There were some errors in my solution.
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal <[email protected]>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.
What I actually meant was "Since n is greater than (k+r)C(r), it means that
the (k+r+1)th bit of nth number is 1"
>
> The problem reduces to finding [n - (m+r)C(r)]
its [n - (k+r)C(r)]
> smallest number than can be formed with (k-1) 1 bits
(and 'r' 0 bits)
To elaborate this critical point. Here is an example.
Let k=4, n=7. i.e. we need to find the 7th number in the series of numbers
with 4 bits set.
Initial call rec(0, 7, 4)
(4+1)C(1) < 7 < (4+2)C(2)
Hence we get sure that (4+1+1)th bit of nth number is 1.
Req number -> 1_ _ _ _ _
now call (0 + 32, 7-5,4-1)
(3+0)C0 < 2 < (3+1)C1
So Req number-> 1 0 1_ _ _
call (32 + 8, 2-1, 3-1)
(2+0)C0 = 1, hence last 2 bits should be 1
hence, Req Number -> 1 0 1 0 1 1
Hence answer is 43.
.
>
> 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
>
--
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
-~----------~----~----~----~------~----~------~--~---
