4 elements with sum 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).
We have discussed a O(n^3) algorithm in the previous post on this topic. The problem can be solved in O(n^2Logn) time with the help of auxiliary space.
Thanks to itsnimish for suggesting this method. Following is the detailed process.
Let the input array be A[].
1) Create an auxiliary array aux[] and store sum of all possible pairs in aux[]. The size of aux[] will be n*(n-1)/2 where n is the size of A[].
2) Sort the auxiliary array aux[].
3) Now the problem reduces to find two elements in aux[] with sum equal to X. We can use method pair of this post to find the two elements efficiently. There is following important point to note though. An element of aux[] represents a pair from A[]. While picking two elements from aux[], we must check whether the two elements have an element of A[] in common. For example, if first element sum of A[1] and A[2], and second element is sum of A[2] and A[4], then these two elements of aux[] don’t represent four distinct elements of input array A[].
Following is C implementation of this method.
#include <stdio.h>
#include <stdlib.h>
// The following structure is needed to store pair sums in aux[]
struct pairSum
{
int first; // index (int A[]) of first element in pair
int sec; // index of second element in pair
int sum; // sum of the pair
};
// Following function is needed for library function qsort()
int compare (const void *a, const void * b)
{
return ( (*(pairSum *)a).sum - (*(pairSum*)b).sum );
}
// Function to check if two given pairs have any common element or not
bool noCommon(struct pairSum a, struct pairSum b)
{
if (a.first == b.first || a.first == b.sec ||
a.sec == b.first || a.sec == b.sec)
return false;
return true;
}
// The function finds four elements with given sum X
void findFourElements (int arr[], int n, int X)
{
int i, j;
// Create an auxiliary array to store all pair sums
int size = (n*(n-1))/2;
struct pairSum aux[size];
/* Generate all possible pairs from A[] and store sums
of all possible pairs in aux[] */
int k = 0;
for (i = 0; i < n-1; i++)
{
for (j = i+1; j < n; j++)
{
aux[k].sum = arr[i] + arr[j];
aux[k].first = i;
aux[k].sec = j;
k++;
}
}
// Sort the aux[] array using library function for sorting
qsort (aux, size, sizeof(aux[0]), compare);
// Now start two index variables from two corners of array
// and move them toward each other.
i = 0;
j = size-1;
while (i < size && j >=0 )
{
if ((aux[i].sum + aux[j].sum == X) && noCommon(aux[i], aux[j]))
{
printf ("%d, %d, %d, %d\n", arr[aux[i].first], arr[aux[i].sec],
arr[aux[j].first], arr[aux[j].sec]);
return;
}
else if (aux[i].sum + aux[j].sum < X)
i++;
else
j--;
}
}
// Driver program to test above function
int main()
{
int arr[] = {10, 20, 30, 40, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int X = 91;
findFourElements (arr, n, X);
return 0;
}
Output:
20, 1, 30, 40
Please note that the above code prints only one quadruple. If we remove the return statement and add statements “i++; j–;”, then it prints same quadruple five times. The code can modified to print all quadruples only once. It has been kept this way to keep it simple.
Time complexity: The step 1 takes O(n^2) time. The second step is sorting an array of size O(n^2). Sorting can be done in O(n^2Logn) time using merge sort or heap sort or any other O(nLogn) algorithm. The third step takes O(n^2) time. So overall complexity is O(n^2Logn).
Auxiliary Space: O(n^2). The big size of auxiliary array can be a concern in this method.