Home » Technical Interview Questions » Array Interview Questions » Four Elements that Sum to Given

Four Elements that Sum to Given


Reading Time - 6 mins


Difficulty Level Medium

In four elements that sum to a given problem, we have given an array containing N elements that may be positive or negative. Find the set of four elements whose sum is equal to given value k.

Input Format

First-line containing an integer N.

Second-line containing an array which contain n elements.

Output Format

A single line containing four integer values separated by space. We can print the order of the element in any way.

Example

Input

6

10 20 30 40 1 2

Output

20 1 30 40

Algorithm for Four Elements that Sum to Given

a. Create a struct that stores two elements and the sum of the elements.

b. Create an auxiliary array of size (n)(n-1)/2, in the auxiliary array store all possible pairs from the input array and sum of them.

c. So, instead of finding all the four elements. We need to find a pair of elements in the new auxiliary whose sum equal to the sum.

d. For finding the pair, sort the array based on the difference between sums.

e. Find the pair now using the same algorithm to find the pair of elements to the given sum.

  • Maintain two-position one at the end of the array and one at the start.
  • Move-in the array to find the sum, if current sum > sum move last position.
  • Else, move first one
READ  Minimum Index Sum of Two Lists

f. Finally, print all the elements whose sum equal to given_value.

C++ Program for Four Elements that Sum to Given

#include <bits/stdc++.h> 
struct pair
{
    int first_element;
    int second_element;
    int Sum;
};
int compareSums(const void *a, const void * b)
{
    return ( (*(pair *)a).Sum - (*(pair*)b).Sum );
}
 
bool isThereCommon(struct pair a, struct pair b)
{
    if (a.first_element == b.first_element || a.first_element == b.second_element || a.second_element == b.first_element || a.second_element == b.second_element)
    {
        return false;
    }
    return true;
}
 
 
void FindFour(int array[], int n, int X)
{
    int i, j;
    int size = (n*(n-1))/2;
    //auxilary array to store sums of elements
    struct pair auxiliary_array[size];
    int k = 0;
    for (i = 0; i < n-1; i++)
    {
        for (j = i+1; j < n; j++)
        {
            auxiliary_array[k].Sum = array[i] + array[j];//sum of elements
            auxiliary_array[k].first_element = i;//index of first element
            auxiliary_array[k].second_element = j;//index of second element
            k++;
        }
    }
    qsort(auxiliary_array, size,sizeof(auxiliary_array[0]),compareSums);
    i = 0;
    j = size-1;
    while (i < size && j >=0 )
    {
        if ((auxiliary_array[i].Sum + auxiliary_array[j].Sum == X) && isThereCommon(auxiliary_array[i], auxiliary_array[j]))
        {
            printf ("%d, %d, %d, %d\n",array[auxiliary_array[i].first_element],array[auxiliary_array[i].second_element],array[auxiliary_array[j].first_element],array[auxiliary_array[j].second_element]);
            return;
        }
        else if (auxiliary_array[i].Sum + auxiliary_array[j].Sum > X)
        {
            j--;
        }
        else
        {
            i++;
        }
    }
}
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
       cin>>a[i];
    }   
    int size = sizeof(a)/sizeof(a[0]);
    int Sum = 91;
    FindFour(a,size,Sum);
    return 0;
}
20, 1, 30, 40

Complexity Analysis for Four Elements that Sum to Given

Time complexity

O(n*n*logn) because we sort the auxiliary array whose size (n*(n-1))/2. And sorting for this array takes n*n*log(n) time.

Space Complexity

O(n*n) because we create auxiliary space to store the sum of all the pairs. Here the total number of pairs is (n*(n-1))/2.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions