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.