Re: [algogeeks] 4Sum
@hemesh, amol = correct solutions ABCDEF another problem on SPOJ, incase people want to try. On Sun, Jun 24, 2012 at 2:13 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ Amol Sharma thanx got it.. yup, overlooked those case's :-) my bad.. On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma amolsharm...@gmail.comwrote: @sourabh: for this particular question.. in your code replace if(binary_search(c,c+size,-b[i])) count++; by count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); you are actually missing some of the quadruplesas there can be more than one element with value -b[i] in the array c and you are actually ignoring them. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.comwrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh:
Re: [algogeeks] 4Sum
@bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.comwrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so
Re: [algogeeks] 4Sum
@ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.com wrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.comwrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and
Re: [algogeeks] 4Sum
@sourabh: for this particular question.. in your code replace if(binary_search(c,c+size,-b[i])) count++; by count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); you are actually missing some of the quadruplesas there can be more than one element with value -b[i] in the array c and you are actually ignoring them. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.comwrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18,
Re: [algogeeks] 4Sum
@ Amol Sharma thanx got it.. yup, overlooked those case's :-) my bad.. On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma amolsharm...@gmail.com wrote: @sourabh: for this particular question.. in your code replace if(binary_search(c,c+size,-b[i])) count++; by count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); you are actually missing some of the quadruplesas there can be more than one element with value -b[i] in the array c and you are actually ignoring them. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.comwrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99
Re: [algogeeks] 4Sum
We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en .
Re: [algogeeks] 4Sum
@KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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. -- Regards, Jalaj Jaiswal Software Engineer, Zynga Inc +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89 LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro -- 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] 4Sum
@Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- 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/-/9jCCN5iHDB8J. 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. -- Regards, Jalaj Jaiswal Software Engineer, Zynga Inc +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89 LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro -- 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/-/SGN_A_YrZlkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email
Re: [algogeeks] 4Sum
@rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@* *googlegr**oups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- 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/-/9jCCN5iHDB8Jhttps://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this
Re: [algogeeks] 4Sum
Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@ **googlegr**oups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- 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/*
Re: [algogeeks] 4Sum
@Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.comwrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J. 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] 4Sum
@hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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] 4Sum
@hemesh :- please explain your approach On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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. -- Utsav Sharma, NIT Allahabad -- 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] 4Sum
The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.comwrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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] 4Sum
@jalag: in amol's solution binary search will take log(n^3) bcz size of sum array is n^3 not it will take n^3*logn . -- 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] 4Sum
Its simple varition of 3 sum problem , using hask table u can easily do it . let s=a+b+c+d can be written as b+c+d=s-a; - 3 SUM Try it let me know i find any difficulty :) On Fri, Jun 15, 2012 at 3:50 PM, Akshat Sapra sapraaks...@gmail.com wrote: Given an array *S* of *n* integers, are there elements *a*, *b*, *c*, and *d* in *S* such that *a* + *b* + *c* + *d* = target? Find all unique quadruplets in the array which gives the sum of target. -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- 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. -- *Thanks Shashank Mani Narayan Computer Science Engineering Birla Institute of Technology,Mesra ** Founder Cracking The Code Lab http://shashank7s.blogspot.com/; FB Page http://www.facebook.com/pages/Cracking-The-Code/148241881919895 Google+ http://gplus.to/wgpshashank Twitter https://twitter.com/wgpshashankhttps://twitter.com/#%21/wgpshashank Puzzled Guy @ http://ashutosh7s.blogspot.com** **FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds* * Key Person Algogeek https://groups.google.com/forum/#!forum /algogeekshttps://groups.google.com/forum/#%21forum/algogeeks **Cell +91-9740852296 * * ** * -- 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] 4Sum
Complexity : O(n^3)
import java.util.*;
public class Solution {
public ArrayListArrayListInteger fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayListArrayListInteger arr=new ArrayListArrayListInteger();
Arrays.sort(num);
int n=num.length;
int sum=0;
for(int i=0;in-3;i++)
{
int a=num[i];
for(int j=i+1;jn-2;j++)
{
int b=num[j];
int k=j+1;
int l=n-1;
while(kl)
{
int c=num[k];
int d=num[l];
if(a+b+c+d target)
k++;
else if(a+b+c+d target)
l--;
else
{
ArrayListInteger al=new ArrayListInteger();
al.add(a);
al.add(b);
al.add(c);
al.add(d);
if(!arr.contains(al))
arr.add(al);
k++;
}
}
}
}
return arr;
}
}
--
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] 4Sum
O(n^3) is straight forward:
find all triplets and store them in an array say sum.
and then for each triplet do binary search for (target-sum[i]) in the given
array.
is solution better than O(n^3) possible ?
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 15, 2012 at 6:53 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
Complexity : O(n^3)
import java.util.*;
public class Solution {
public ArrayListArrayListInteger fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayListArrayListInteger arr=new ArrayListArrayListInteger();
Arrays.sort(num);
int n=num.length;
int sum=0;
for(int i=0;in-3;i++)
{
int a=num[i];
for(int j=i+1;jn-2;j++)
{
int b=num[j];
int k=j+1;
int l=n-1;
while(kl)
{
int c=num[k];
int d=num[l];
if(a+b+c+d target)
k++;
else if(a+b+c+d target)
l--;
else
{
ArrayListInteger al=new ArrayListInteger();
al.add(a);
al.add(b);
al.add(c);
al.add(d);
if(!arr.contains(al))
arr.add(al);
k++;
}
}
}
}
return arr;
}
}
--
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] 4Sum
Find all b[k]=a[i]+a[j] for the given array a.
Iterate over all elements of this array b.
Let the sum be (a+b). Now binary search (target - (a+b) ) in the array b.
Complexity : O( (N^2)( log (N^2) ) )
Correct me if i am wrong.
On Fri, Jun 15, 2012 at 8:41 PM, Amol Sharma amolsharm...@gmail.com wrote:
O(n^3) is straight forward:
find all triplets and store them in an array say sum.
and then for each triplet do binary search for (target-sum[i]) in the
given array.
is solution better than O(n^3) possible ?
--
Amol Sharma
Final Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99
On Fri, Jun 15, 2012 at 6:53 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
Complexity : O(n^3)
import java.util.*;
public class Solution {
public ArrayListArrayListInteger fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayListArrayListInteger arr=new ArrayListArrayListInteger();
Arrays.sort(num);
int n=num.length;
int sum=0;
for(int i=0;in-3;i++)
{
int a=num[i];
for(int j=i+1;jn-2;j++)
{
int b=num[j];
int k=j+1;
int l=n-1;
while(kl)
{
int c=num[k];
int d=num[l];
if(a+b+c+d target)
k++;
else if(a+b+c+d target)
l--;
else
{
ArrayListInteger al=new ArrayListInteger();
al.add(a);
al.add(b);
al.add(c);
al.add(d);
if(!arr.contains(al))
arr.add(al);
k++;
}
}
}
}
return arr;
}
}
--
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.
--
Hemesh singh
--
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] 4Sum
@hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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.
