Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution) | GeeksforGeeks

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.

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 1 ofthis 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[].

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

    }

}

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.

Read full article from Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution) | GeeksforGeeks