Four Elements that Sum to Given

Problem Statement

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

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

Implementation

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;
}

Java Program for Four Elements that Sum to Given

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
class sum
{
    static class pair {
        int first, second;
        public pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
    public static void findFourElements(int arr[], int n, int X)
    {
        HashMap<Integer, pair> mp = new HashMap<Integer, pair>();
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                mp.put(arr[i] + arr[j], new pair(i, j));
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = arr[i] + arr[j];
                if (mp.containsKey(X - sum)) {
                    pair p = mp.get(X - sum);
                    if (p.first != i && p.first != j
                        && p.second != i && p.second != j) {
                        System.out.println(
                            arr[i] + " " + arr[j] + " "
                            + arr[p.first] + " "
                            + arr[p.second]);
                        return;
                    }
                }
            }
        }
        System.out.println("No Solution");
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int sum ;
        sum = sr.nextInt();
        findFourElements(arr,n, sum);
    } 
}

6
10 20 30 40 1 2
91

20 30 40 1

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.