Its a bit similar to finding the rank of the word "COMPUTER" in the
dictionary among the words formed from C,O,M,P,U,T,E,R.
Find maximum r such that (k+r)C(r) < n.
This represents the total number of numbers formed from 'r' 0 bits and 'k' 1
bits. Since n is greater, it implies it has an extra 1 bit in its
representation.
The problem reduces to finding [n - (m+r)C(r)] smallest number than can be
formed with (k-1) 1 bits.
here is a recursive function to obtain the result.
int rec(int curr, int n, int k){
int r,j,comb,tmp;
if(n==1)
return curr+((1<<k) - 1); /* 1st number in the sequence with m bits. */
for(r =1,comb = 1; ; r++)
{
tmp = (comb*(k+r))/r; /* k+rCr = (k+r-1)C(r-1) x (k+r)/r */
if(tmp == n)
return curr + (1<<(k+r)) - (1<<r); /* All the 'k' left most bits
should be 1 and rest 0 */
else if(tmp > n)
return rec(curr+(1<<(k+r-1)), n-comb,k-1);
comb= tmp;
}
}
Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal
<[email protected]>wrote:
>
> Nth number with K set bits
> We are given with k number of set bits (bit=1). We have to find the Nth
> number which has k set bits.
>
> for example
>
> k=3
>
> the numbers with k set bits are as follows:
>
> 000111 = 7
> 001011 = 11
> 001101 = 13
> 001110 = 14
> 010011 = 19
> 010101 = 21
> 010110 = 22
> 011001 = 25
> 011010 = 26
> 011100 = 28
> ....
> and so on....
>
> we have to find the Nth number in this series...
>
> suggest some method
>
> >
>
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
