Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
yea i know 1st Approach is much better and is Only O(N^2) for precomputing all the values for nck and then O(k) for finding no of bits set in The Kth number and another loop of O(k) to find the required number i posted 2nd approach in the context to vandana's tree approach of sorting 2^N numbers, rather simply sort the numbers in the array... and this approach is O(N*2^N) On 10/21/11, sravanreddy001 sravanreddy...@gmail.com wrote: @Sunny.. why do we need an O(2^N) complexity? for a value of N=40-50, the solution is not useful.. but, your 1st approach is lot better and i have got it too.. 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1-k (n C i)) 2. again, keep substracting (k-i) for i= 0-k-1 so.. O(k) here and recursively performing step 2. (worst case complexity is O(T)) where T = nCk O(N) + O(T) == O(T) as it dominates the given number. unless it doesn't fall in the range.. or equivalently -- max( O(T), O(N) ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J. 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. -- 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 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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
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.comwrote:
*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:*
110
--
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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
although input is small so a brute force will also do
but some optimization can be like
1. first we can find that how many bits will be set in Kth Codewords using
the following method
no of codewords with N bits set = 1
no of codewords with N-1 bits set = NC1
no of codewords with N-2 bits set = NC2
.
.
.
no of codewords with 1 bits set = NC1
no of codewords with 0 bits set = 1
using these precomputed counts we can get index of the element in the all
numbers having k bits set
so problem will reduce to find the ith element with j bits set
first element of the sequence will be (N-j) 0's followed by j ones then we
can use i-1 calls NextHigherNumberWithSameBitsSet function to get the
required number
again there is one more optimization possible rather than calling function
i-1 times, search archives for the implementation
On Wed, Oct 19, 2011 at 9:03 PM, aritra kundu aritra2123...@gmail.comwrote:
*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:*
110
--
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.
--
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 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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
Completing it... Got sent before I completed
On Wed, Oct 19, 2011 at 12:31 PM, Vandana Bachani vandana@gmail.comwrote:
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.comwrote:
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.comwrote:
*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:*
110
--
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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
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+(1n), cmp);
On Wed, Oct 19, 2011 at 10:46 PM, Vandana Bachani vandana@gmail.comwrote:
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.comwrote:
*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:*
110
--
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.
--
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 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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
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 vandana@gmail.comwrote:
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.comwrote:
*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:*
110
--
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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
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:*
110
--
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.
Re: [algogeeks] FACEBOOK ONLINE CODING ROUND
yes u r wrong
11
111 = 110 but sequence will be
11
101
110
On Thu, Oct 20, 2011 at 12:18 AM, tin a.gu...@tin.it wrote:
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.comwrote:
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.comwrote:
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.comwrote:
*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:*
110
--
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.
--
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.
--
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 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.
