Re: [algogeeks] sum to 0
@sharad Can you explain the O(n*n) + O(n) space algorithm that you mentioned? -- 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.
Re: [algogeeks] sum to 0
@senthilnathan prepare a hash table for the third array now pick any element 4m array 1 add it to 1 element of array 2 now try to find -(m+n) in hash table since every element of arr1 will be sum to every arr of array2 and lookup in hash table to be O(1) so overall complexity will be O(n2) time+O(n) space -- 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.
Re: [algogeeks] sum to 0
@ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this 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.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 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.
Re: [algogeeks] sum to 0
@algoose chase: you're right thx for the test case On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote: @ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this 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.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 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.
Re: [algogeeks] sum to 0
sort array c only. now select every pair from array a nd b ( o(n2)) for every pair find the element from c which gives sum of the three element 0. ( search using binary search as c is sorted) so the algo is O (n^2 logn)) On 16 June 2010 13:47, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @algoose chase: you're right thx for the test case On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote: @ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this 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.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 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.
Re: [algogeeks] sum to 0
@^ he has already asked to optimize n^2logn solution On Wed, Jun 16, 2010 at 5:25 PM, divya jain sweetdivya@gmail.comwrote: sort array c only. now select every pair from array a nd b ( o(n2)) for every pair find the element from c which gives sum of the three element 0. ( search using binary search as c is sorted) so the algo is O (n^2 logn)) On 16 June 2010 13:47, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @algoose chase: you're right thx for the test case On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote: @ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this 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.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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.
Re: [algogeeks] sum to 0
plzzz comment on this 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.
Re: [algogeeks] sum to 0
sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this 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. -- 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] sum to 0
Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination. both o(n2)+o(n)space and o(n2logn)+o(1)space are trivial but can we optimise more -- 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.
