Nkk's Problem
I mean, this was a problem that Nkk had found somewhere and sent me long long ago. I found it yesterday on my machine. Here it is.
There is a series of numbers in ascending order. All these numbers have the same number of binary '1's in them. Given the number of 1 bits set in the numbers (say k), write an algorithm/C program to find the nth number in the series.
It is pretty simple. It demonstrates a nice property of the '1's in binary representation, nonetheless.
I think you have to start pushing 0s from the MSB to get the next series of numbers.
For instance, if k=4, the smallest binary number is 1111. The next smallest is 10111, the next is 11011 and so on. Once the 0 reaches the last position, we can start pushing another 0.
Is that right?
Posted by
Srinath Srinivasa |
7:59 PM, January 17, 2006
Right observations. But the way I percieved it is slightly different. The smallest no. is 0*1(ktimes). Observe the way the 1's move. They start in a 'cluster', then they 'uncluster' one by one, then they 'recluster' by togeter moving one position to the left, thus pushing a 0 to the right.
Initially, there are 0 0s to the right. After every period of k, (during which the 1s move to the left and push a 0 to the right one step each) one 0 is pushed to the right of the 1's cluster.
So, if you consider k=4, the 22nd number (or 23rd, depending on how you start your enumeration) in the series would be - 22/5 = 4, 2. That is, 4 0's at the end of the cluster. And the 1's cluster is partitioned by a 0 after the 2nd position.
The no. - 110110000
Posted by
Anonymous |
11:20 PM, January 17, 2006
Oops... there is a mistake above. The nth no. can be obtained through the relation - n/k. In the above example, it is 22/4, and not 22/5. So, the no. is 1101100000.
Thanks Nkk.
Posted by
Anonymous |
4:14 AM, January 18, 2006