Find the number of set bits in the binary equivalent of a decimal number. The solution is required to be O(1) in both time and space. here is a slick solution. Although it is claimed here that it is nearly O(1), I’m not sure the judges would have accepted it.
For any unsigned number b, n is the number of signed bits, and n is calculated as follows:
for(n=0; b; b >>= 1)
if (b & 1) n++;
Un more. From an infinte bit stream, determine whether the decimal equivalent of the binary obtained so far is divisible by three.
Sum the even and odd bits separately. If their difference is divisible by three, so is the number. You can obtain the result by considering the number is represented as Summatuion over(3-1)^n instead of the usual Sum over 2^n, and then expanding using binomial expansion.
Too bad, this didn’t strike me during the event. More problems will be posted. You are free to request or even send interesting Qs to me.
The way you posted to count the no of bits is O(b) where is b is the no of bits in the number.
There is another way to get it in O(k) where k is the number of 1s in the number
Try it 
Comment by vijay03 — September 9, 2008 @ 11:53 am |
Thanks a lot for bringing to my notice that there is a O(k) solution. I didn’t think there was something special about the algorithm I has posted previously, however, here’s the better algorithm
It works by setting the rightmost bit to zero.
here’s a good reference on set-bit counting.
Comment by Sanjeev Chandran — September 11, 2008 @ 1:30 pm |