Sum of four elements equals X
Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).
Note: Numbers should not be overlapping. eg(3,5,7,4) will generate 3+5=8 and 5+7=12 , for sum equals 20, 5 is overlapping.
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).
Note: Numbers should not be overlapping. eg(3,5,7,4) will generate 3+5=8 and 5+7=12 , for sum equals 20, 5 is overlapping.
A solution running in O(N^3)time and constant space can be easily seen.
ReplyDeleteThe best solution for this problem runs in O(N^2LogN) and O(N^2) space is:-
Make a vector of size N*(N-1)/2.
Here we will keep the pairwise sum of each element of the array.
But the elements of the vector are
typedef pair< int, pair > PIPII ;
and vector is V pairsum;
Here the first element is the pairwise sum and second element stores the indexes whose pairwise sum is stored.
Now, we just need to find two elements from this vector whose sum is X.This can be done in linear time. For this we need to sort the vector.
Now ,when we get the two elements whose sum is X, we need to make sure that the indexes are not overlapping. This can be done by checking the two indexes of both elements.
Total time complexity :- N^2 [for making pairwise sum ] + 2*N^2LogN [sorting the vector] + N^2[finding the two elements whose sum is X] => O(N^2LogN)
Caution :- Although this algorithm reduces the time complexity from O(N^3) to O(N^2LogN), space complexity is N^2 , which is high.
@Navin when you say make sure indexes are not overlapping does it mean their values should not be the same. If it is then think of the scenario where the common elements could be repeating as well.
ReplyDelete@Admin , indexes means the position of the element in the array. It can't be repeating in the array.
ReplyDeleteFor ex :-
suppose ur array is :- 3,5,6,7,
here pairwise sum is 8,9,10,11,12,13
Now if the required sum is 17.Although 8+9 = 17. But this doesnot make a valid result because the indexes of the individual elements of the pairwise sum is overlapping.
8 is formed by 3 & 5 i.e. arr[0] & arr[1]
9 is formed by 3 & 6 i,e, arr[0] & arr[2]
Here the index 0 is overlapping. Hence the result does not contain unique 4 elements although the required Number is obtained from sum of pairwise sums.Hence discarded.
I hope I am clear now.