Can you just generate them sorted?
1 is the minimum
1 << 1 is the next in line
1 << 2 is the next one
1 << N
11
11 << 1
and so on
Am i wrong?
Il 19/10/2011 19:33, Vandana Bachani ha scritto:
Completing it... Got sent before I completed
On Wed, Oct 19, 2011 at 12:31 PM, Vandana Bachani
<vandana....@gmail.com <mailto: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 <mailto: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 <mailto: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
<mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto:algogeeks%2bunsubscr...@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.
--
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.
