[algogeeks] Re: Subset sum...doubt.
It looks like finding all subsets of a set which satisfy a condition
(sum is ZERO).
Using bit approach
i.e.
01101 == 120,150, 316
10100 == -466, 150
int main(int argc, char *argv[])
{
int sum = 0;
int tmp=0;
int i=0;
int a[10]={-466, 120, 150, 421, 316};
int length = 5;
int no_of_subset=31;
char subset[50];
while (no_of_subset=1)
{
sum=0;
tmp=no_of_subset;
subset[0]=0;
for(i=length-1;i=0;i--)
{
if(tmp 1)
{
sum += a[i];
sprintf(subset,%s %d,,subset,a[i]);
}
tmp = tmp 1;
}
if(sum==0)
printf(subset: %s ,subset);
no_of_subset--;
}
return 0;
}
We can also use recursive approach (finding subsets recursively)
--
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.
[algogeeks] Re: Bit Manipulation
Yes, I guess following correction in step 1 for Next Smallest should fix it: 1. Find the leftmost 1 [ Not rightmost]. On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: Bit Manipulation
Yes, I guess following correction in step 1 for Next Smallest should fix it: 1. Find the leftmost 1 [ Not rightmost]. On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: Bit Manipulation
Yes, Following should do for next smallest: 1. Find rightmost 01 pair 2. swap these two bits (make it 10) e.g. N=3(011), Next smallest: 5(101) N=10(1010), Next smallest: 12(1100) N=14(01110), Next Smallest: 22(10110) On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store clind count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store clind count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store child count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store child count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: amazon questions
For 2nd question (probability): Looks like one data is missing for C. If I assume C can shoot 8 out of 10. times then: P(A) = 4/5 P(B)=6/7 P(C)=8/10 Required Probability should be = P(A) * P(B) + P(B) * P(C) + P(A) * P(C) On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: kth largest in tree
That's right. Tks. But looks like above algorithm is for kth smallest.
Not kth largest.
That's why I mentioned inorder traversal as right_child -- parent
--
left_child.
Not usual way: left_child -- parent --
right_child
On Jan 12, 1:08 am, juver++ avpostni...@gmail.com wrote:
If modification of the tree is allowed then each query can be solved in
O(height).
find(node, k) {
if (count(node-left) + 1 == k) result = node;
else if (count(node-left) k) result = find(node-right, k
- count(node-left) - 1);
return find(node-left, k);
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: MICROSOFT IDC
sort both linked lists using non-recursive merge sort: Time: O(nlogn), Space: O(1) Then while both lists are not null loop if list1-data == list2-data then print/store list1-data move list1 pointer one node further move list2 pointer pne node further else if list1-data list2-data then move list1 pointer one node further else move list2 pointer one node further done On Jan 12, 2:23 am, Aniket aniket...@gmail.com wrote: Find the intersection of two unsorted singly linked list in O(1) space and less than O(n^2) complexity. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b2,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern all elements for following while shuffling. All elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted, b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)-1] where N i = 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[3], a[8], a[4], a[9], a[5], a[10], a[6], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = A[current_index]; current_index = to_index; while all elements are done Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b1,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern all elements for following while shuffling. All elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted, b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)-1] where N i = 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[3], a[8], a[4], a[9], a[5], a[10], a[6], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = A[current_index]; current_index = to_index; while all elements are done Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b1,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern all elements for following while shuffling. All elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted, b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)] where N i 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[3], a[8], a[4], a[9], a[5], a[10], a[6], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = A[current_index]; current_index = to_index; while all elements are done Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b1,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern all elements for following while shuffling. All elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted, b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)] where N i 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[3], a[8], a[4], a[9], a[5], a[10], a[6], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = A[current_index]; current_index = to_index; while all elements are not done Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b1,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern for all elements while shuffling. For all elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted,b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)] where N i 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = A[current_index]; current_index = to_index; while all elements are not done Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Adobe - Algorithm
OK. I hope following should do the needful. Input: a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN Output: a1,b1,a2,b2,a3,b3,a4,b4,..aN,bN. If we notice, there is a pattern for all elements while shuffling. For all elements from 1st half portion (a1 to aN) a[i] is moved to a[2*i] where 0= i = N [say array name is a] i.e. a[0] is moved to a[0] (for i=0, i = 2*i =0) a[1] is moved to a[2] a[2] is moved to a[4] a[3] is moved to a[6] .. For 2nd half, same is true from opposite (OR if we see array inverted,b1 to bN behaves same as a's) In other words, keeping array as is, 2nd half of the array (b1 to bN) goes like this a[i] is moved to a[n-2*(n-i)] where N i 2N i.e. (Assuming 2nd half array starting with index i=7, so total array size 12) a[7] moved to a[1] a[8] moved to a[3] a[9] moved to a[5] overall as example: Input a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11] Output: a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5], a[11] And I believe it's pretty straightforward to implement this. using only few extra variables [not dependent on array size](Based on implimentation). So, O(n) time and O(1) space. Alg: [assuming all elements are 0) Negate all elements (a[i] = -1 * a[i];) current_index = 0; current_element=A[0]; do if current_index = n/2 then to_index = 2*current_index else to_index = (size -1) - 2*(size - 1 - current_index) end if current_element = A[to_index]; A[to_index] = -1 * A[current_index]; if current_element 0 then to_index = index of next negative element. current_index = to_index; while A[current_index] 0 Algo can be modified to check in other cases like when elements can be negative also, OR elements are characters, strings. There can be different ways to track if all elements are processed or not, depending on problem. e.g. if negative elements are also in input then, Add some very very negative no to all elements say -5 and while assigning it to to_index, adding 5 If element are characters, string then attach some keyword (prefix or suffix) to each element, while assigning it to to_index, remove the attachment. Please advise if you find any issue with this. On Jan 10, 5:51 pm, juver++ avpostni...@gmail.com wrote: There is only one single array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Single linked list questions.
Hi, I'm new here and looking to learn more on algos and participate in
discussions.
@juver++, Recursion solution to the 1st problem implicitly using
stack. No?
print (list l)
{
if(i-next) print(l-next);
print l;
}
On Jan 6, 4:55 pm, juver++ avpostni...@gmail.com wrote:
1. Recursive function. Print node's element after processing next link of
the current node. Also this can be achieved using stack.
2. Please clarify the question.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
