Better logic:
create a list array of lists (like a hash table with lists). Array size is N
represents 1 to N bits and lists that will increase as we add more elements
to it.
for(i = 1; i < 2^N; i++)
{
c = count no. of 1s. in i
}
On Wed, Oct 19, 2011 at 12:16 PM, Vandana Bachani <[email protected]>wrote:
> 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 <[email protected]>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 [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?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 [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?hl=en.
