No need of creating a tree
simply take an array of size 2^N in which all a[i] initialized to i
now sort the array first depending upon the set bits in the a[i] if set bits
are equal then use value
this function call to sort function of algorithms will do the required
bool cmp(int x, int y){
int count1 = __builtin_popcount(x);
int count2 = __builtin_popcount(y);
if(count1 < count2) return true;
if(count1 > count2) return false;
return x < y;
}
call in main
sort(a,a+(1<<n), cmp);
On Wed, Oct 19, 2011 at 10:46 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.
>
--
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 [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.
