although input is small so a brute force will also do
but some optimization can be like
1. first we can find that how many bits will be set in Kth Codewords using
the following method
no of codewords with N bits set = 1
no of codewords with N-1 bits set = NC1
no of codewords with N-2 bits set = NC2
.
.
.
no of codewords with 1 bits set = NC1
no of codewords with 0 bits set = 1
using these precomputed counts we can get index of the element in the all
numbers having k bits set
so problem will reduce to find the ith element with j bits set
first element of the sequence will be (N-j) 0's followed by j ones then we
can use i-1 calls NextHigherNumberWithSameBitsSet function to get the
required number
again there is one more optimization possible rather than calling function
i-1 times, search archives for the implementation
On Wed, Oct 19, 2011 at 9:03 PM, aritra kundu <aritra2123...@gmail.com>wrote:
> *Question 1 / 1*
> Given an integer *N*, there are *2^N* binary codewords of length N. All of
> them are taken and sorted to create a sequence: Sort by the number of 1-bits
> in the codeword bit-string. If there is a tie, break tie so that the smaller
> number comes first in the output sequence
>
> *Testcases format:*
> You would be given 2 integers *N* (<=10) and *K* (1 <= K <= 2^N)
> Output the codeword with index K into this sequence
> The input is from stdin and output to stdout
>
> *Sample Testcases:*
> *Input #00:*
> 3 5
> *Output #00:*
> 011
> *Explanation:*
> For N = 3, the sequence consists of {000,001,010,100,011,101,110,
> 111}. The 5th indexed number would be 011
>
> *Input #01:*
> 7 127
> *Output #01:*
> 1111110
>
> --
> 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?hl=en.
>
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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?hl=en.
