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.
1 Like
Is the number given in decimal representation?
1 Like
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
1 Like
@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++…
2 Likes
__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
3 Likes
Yes, its given in decimal
The main task is to solve this question in standard way. Please don’t think that python will do anything.
1 Like
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).
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 
@hemanth_1 bro can you send me the code of yours. I want to have a look even i got stuck at a problem where it require to find the # of set bits for a very large number. Thank you 
I know its been long 
but i pls help me.