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

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.