@shishir
plz give an example..
its bit tough to understand for me atleast..
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal <1987.shis...@gmail.com>wrote:
> 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 <ankur.mast....@gmail.com
> > 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
