@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
@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
@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 --
@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
@ 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
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
@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,
@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
@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
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
@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
@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
@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
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
@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
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*
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
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
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
@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
20 matches
Mail list logo
