Hi,
logic:
We can work on this problem from the way we construct the sequence.
First we generate a binary tree such that each leafnode corresponds to one
of the 2^N nodes. We start we an empty root, creating 0, 1 nodes assigning
one bit at a time upto N levels (there would be 2^N - leafnodes) but while
doing that we can assign weights and values to each node as we construct the
tree. (In a breadth first fashion). node.weight = node.parent.weight + 0/1
(based on whether it lies on the 0th edge (left edge) of the parent or the
1th edge (right edge) of the parent, we can say 0 ad 1 are respective edge
weights) and node.value = node.parent.value*2 + 0/1.
We will add the leaf nodes to an array(sequence) as they get created when we
reach "nth" level in the tree. Sort the array of nodes by weight and by
value in case of tie.
-Vandana
On Wed, Oct 19, 2011 at 10:33 AM, 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.
>
--
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.
