By ‘Large’, I mean numbers containing up to 10^4 digits.

I have tried doing it by converting the number to binary, digit by digit (representing numbers as a vector of bits), so I multiply the current result by 10 and add the next digit, which I have done by adding two numbers, left shifted 3 times and 1 time(because N*10 = N<<3 + N<<1) and then wrote a function that adds two binary numbers represented this way, and then add the next digit. But its too slow.

Is the number given in decimal representation?

Yes, its given in decimal

You can simply find it in log(N) complexity by dividing it by 2 , But you have to do this operation in array representation of number

@hemanth_1

well,I would love to do it in python as…

n=int(input())

b=bin(n)

ans=b.count(“1”)

print(ans)

Still u can find the way it could be done in c++…

The main task is to solve this question in standard way. Please don’t think that python will do anything.

If I represent the number as an array, and say, it has ‘N’ digits, wouldn’t division by 2 take O(N) time ? and I’d have to do it Log 10^N times, which will roughly be the number of digits itself (correct me if I’m wrong).

`__builtin_popcount()`

There is a built in gcc function called `__builtin_popcount()`

which can calculate the set bits of a given number represented in decimal.

i.e

```
include <iostream>
using namespace std;
int main() {
cout << __builtin_popcount(15);
return 0;
}
```

Output : 4

Have u frame this question by yourself? Or it is been given somewhere?

we are talking about 10^4 digits here

This was in a contest, I was not able to solve it

Got it accepted just now, it was slow because of the vector, I didn’t consider the fact that insertion at front is slow with it, used a deque instead and it got accepted