Given a vector of maximum 10 000 natural and distinct numbers, find 4 numbers(a, b, c, d) such that a + b + c = d.

Question

Hi,

I solved this problem by following a straightforward but not optimal algorithm. I sorted the vector in descending order and after that substracted numbers from max to min to see if I get a + b + c = d. Notice that I haven't used anywhere the fact that elements are natural, distinct and 10 000 at most. I suppose these details are the key. Does anyone here have a hint over an optimal way of solving this?

Thank you in advance!

Later Edit: My idea goes like this:

'<<quicksort in descending order>>'

for i:=0 to count { // after sorting, loop through the array
    int d := v[i];
    for j:=i+1 to count {
        int dif1 := d - v[j];
        int a := v[j];

       for k:=j+1 to count {
           if (v[k] > dif1)
              continue;
           int dif2 := dif1 - v[k];
         b := v[k];

    for l:=k+1 to count {
 if (dif2 = v[l]) {
    c := dif2; 
     return {a, b, c, d}
 }
           }
        }
    }
}

What do you think?(sorry for the bad indentation)

Answer 1

Solution in O(n² log n):

Compute sets of all possible sums and differences:

{a_i+a_j: 1 <= i,j <= n}

{a_i-a_j: 1 <= i,j <= n}

(store them in a balanced binary search tree) and check if they have a common element. If yes, there are i,j,k,l such that a_i + a_j = a_k - a_l, that is a_i+a_j+a_l=a_k.

Solution in O(a_n log a_n), where a_n is the largest number in the vector:

Compute the polynomial

(x^a₁+x^a₂ + ... + x^a_n)³

you can do it in O(a_n log a_n) using Fast Fourier Transform (first compute square, then third power; see here for description). Observe that after multiplication a coefficient x^b_i was formed from multiplication x^a_i * x^a_j * x^a_k= x^a_i+a_j+a_k for some i,j,k. Check if there is a power x^a_l in the resulting polynomial.

Unfortunately this allows some i,j,k to be used twice. Subtracting 3(x^2a₁+...+x^2a_n)*(x^a₁+...+x^a_n) - 2(x^3a₁+...+x^3a_n) will remove those x^a_i+a_j+a_k.

Answer 2

There is an algorithm by Shamir and Schroeppel that solves this problem in time O(N^2) and with memory O(N), when N is the number of inputs. It basically is what sdcvvc proposes, but instead of storing the sets {a_i + a_j} as a whole one would repeatedly compute only the sums in appropriate intervals. This saves memory, but does not increase the time complexity.

Richard Schroeppel, Adi Shamir: "A T=O(2^(n/2)), S=O(2^(n/4)) Algorithm for Certain NP-Complete Problems". SIAM J. Comput. 10(3): 456-464 (1981)

Answer 3

Here's @MicSim's comment to @sdcvvc's answer implemented in Python:

def abcd(nums):
    sums = dict((a+b, (a,b)) for a, b in combinations(nums, 2))

    for c, d in combinations(sorted(nums), 2): # c < d
        if (d-c) in sums:
            a, b = sums[d-c]
            assert (a+b+c) == d
            if a == c or b == c: continue # all a,b,c,d must be different
            a,b,c = sorted((a,b,c))
            assert a < b < c < d
            return a,b,c,d

Where combinations() could be itertools.combinations() or

def combinations(arr, r):
    assert r == 2 # generate all unordered pairs
    for i, v in enumerate(arr):
        for j in xrange(i+1, len(arr)):
            yield v, arr[j]

It is O(N²) in time and space.

Example:

>>> abcd(range(1, 10000))
(1, 2, 3, 6)