Completing it... Got sent before I completed
On Wed, Oct 19, 2011 at 12:31 PM, Vandana Bachani <vandana....@gmail.com>wrote:
> Better logic:
> create a list array of lists 'arr' (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. a.
> for(i = 1; i <= 2^N; i++)
> {
> c = count no. of 1s. in i
> add i to list arr[c-1].
>
}
>
for (i = 0; i < N; i++)
{
print list arr[i]
}
>
> On Wed, Oct 19, 2011 at 12:16 PM, Vandana Bachani
> <vandana....@gmail.com>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
>> <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.
