find four elements in array whose sum equal to a given number X [closed]

Question

I need help to find an algorithm that finds:

• four elements in array
• whose sum equal to a given number X
• in O(n^2*log(n))

prefer in pseudo-code or c,c++

Answer 1

Abusing the fact that no memory constrain is specified. And using the usual divide and conquer approach.

Number of all permutations for 4 number subsets is C(n,4) and is O(n^4). Number of all permutations for 2 numbers is C(n,2) and is O(n^2). O(n^2) seems to be OK for the task.

1. Input is: an array A with n elements, X.
2. Generate all permutations for 2 number subsets (that's O(n^2)) and put their sums into array B with n^2 elements (also remembering the subsets). Let's denote as S[B[i]] the subset (consisting of the two numbers) whose sum is B[i].
3. Sort the B, O(n^2*log(n^2)).

4. Walk through the array B (O(n^2)) i = [0,n^2) and quick search O(log(n^2)) = O(log(n)) in it for the value (X - B[i]). There might be several of them (but not more than n^2).

   4.1. Walk through all the elements with value of (X - B[i]), using index k.

   4.2. Skip the elements B[k] where S[B[k]] intersects with S[B[i]]. Intersection of two sets with two numbers can be calculated in O(1).

   4.3 If k is the index a element where B[i] + B[k] == X and S[B[k]] doesn't intersect with S[B[i]], then the sum of the sets S[B[k]] and S[B[i]] are the four sought numbers.

Performance is: O( n^2 + n^2*log(n^2) + n^2*log(n^2) ) = O( n^2 * log(n^2) ) = O( n^2 * log(n) )

On step four, when we iterate over the multiple matching elements of B using nested loop. Yet, total number of iterations of the two nested loops is limited by the |B| which is O(n^2). The quick search is not the usual variation but the one which finds the matching element with the lowest index. (Alternatively one can use the usual bsearch and since we might have landed in the middle, use two adjacent loops, checking elements in both directions.)

Answer 2

You can do it in O(n^2). Works fine with duplicated and negative numbers.

edit as Andre noted in comment, time is with use of hash, which has 'worst case' (although it's less likely than winning in a lottery). But you can also replace hashtable with balanced tree (TreeMap in java) and get guaranteed stable O(n^2 * log(n)) solution.

Hashtable sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it's empty, we'll populate it on the way.

for (int i = 0; i < n; ++i) {
    // 'sums' hastable holds all possible sums a[k] + a[l]
    // where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        // Now we need to find if there're different numbers k and l
        // such that a[k] + a[l] == rest and k < i and l < i
        // but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            // found it
        }
    }

    // now let's put in 'sums' hashtable all possible sums
    // a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

Let's say, X = a[1] + a[3] + a[7] + a[10]. This sum will be found when i = 7, j = 10 and rest = a[1] + a[3] (indexes 1 and 3 will be found from hash)