CODEWITHSUNDEEP
algorithmlanguage-agnostic
John
John

Reputation: 4706

Two numbers sum to the third

Given an array of integers [a1 a2 ... an], not necessarily distinct, give an algorithm that returns "yes" if there are distinct indices i,j,k such that ai + aj = ak, and "no" otherwise.

Is there a way to do this faster than brute force, which takes O(n^3)?

Upvotes: 1

Views: 584

Answers (4)

Daniel Le
Daniel Le

Reputation: 1830

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool SUM3(vector<int> &v)
{
  sort(v.begin(), v.end());

  for (int i = 0; i < v.size(); ++i) {
    int j = 0, k = v.size() - 1;

    while (j < k) {
      int result = v[j] + v[k] - v[i];

      if (result < 0 || i == j) ++j;
      else if (result > 0) --k;
      else return true;
    }
  }

  return false;
}

int main()
{
  int a1[] = {25, 7, 9, 2, 4, 8, 10};
  vector<int> v1(a1, a1 + sizeof a1 / sizeof a1[0]);

  printf("%s\n", SUM3(v1) ? "true" : "false");

  int a2[] = {1, 2, 4};
  vector<int> v2(a2, a2 + sizeof a2 / sizeof a2[0]);

  printf("%s\n", SUM3(v2) ? "true" : "false");
  return 0;
}

The complexity of this algorithm is O(n ^ 2).

Upvotes: 0

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

The following python code implements a method similar to that stated by alestanis, and similar to the quadratic algorithm given in the wikipedia article mentioned by Daniel Le. For large uniformly random positive integers, the stated O(n^2) complexity seems to hold. (The inner search loop that increments k executed, on the average, about (n^2)/4 times.) Output from a timed sample run under linux on an old AMD Athlon 5000 processor appears first, followed by the code.

0.002519    N 50    NN 2500     ops 607     NN/ops 4.1186   NN/t 992405.8   Matches 0
0.00752     N 100   NN 10000    ops 1902    NN/ops 5.2576   NN/t 1329794.2  Matches 0
0.035443    N 200   NN 40000    ops 10648   NN/ops 3.7566   NN/t 1128570.5  Matches 2
0.063056    N 400   NN 160000   ops 37403   NN/ops 4.2777   NN/t 2537427.4  Matches 33
0.176328    N 800   NN 640000   ops 163247  NN/ops 3.9204   NN/t 3629595.6  Matches 244
0.729919    N 1600  NN 2560000  ops 658122  NN/ops 3.8899   NN/t 3507238.7  Matches 2062
2.720713    N 3200  NN 10240000     ops 2535751     NN/ops 4.0383   NN/t 3763719.4  Matches 16178
11.07818    N 6400  NN 40960000     ops 10160769    NN/ops 4.0312   NN/t 3697358.2  Matches 128793

import random, bisect, time
V, W, N, Nlim = 500, 500000, 50, 6400
while N <= Nlim:
    t0 = time.time()
    U=sorted([random.randint(V,V+W) for i in range(N)])
    bigsum = U[-1]
    U.append(N*W)
    matches = ops = 0
    for i, ai in enumerate(U[:-2]):
        k = bisect.bisect_right(U, ai+U[i+1])
        for j, aj in enumerate(U[i+1:-1]):
            while ai+aj > U[k]:
                k += 1
                ops += 1
            if U[k] == ai+aj:
                #print 'Match', i, j, k, ai, aj, ai+aj, U[k]
                matches += 1
            if ai+aj > bigsum:
                break
    et = time.time() - t0
    print round(et,6), '\tN',N, '\tNN', N*N, '\tops', ops, '\tNN/ops',
    print round(float(N*N)/ops,4), '\tNN/t', round(N*N/et,1), '\tMatches', matches
    N *= 2

The code probably should be rewritten following the wikipedia outline; a rewrite might clean up some of the awkward array-slice numbers and extraneous completion checks.

Upvotes: 0

HugoRune
HugoRune

Reputation: 13799

  • build a list of all possible sums ai + aj: O(n^2).
    The list wil have size=n^2

  • then compare that list with the array, to see whether there are any similarities:

    • first sort each list: O((n^2)log(n^2)) + O(nlogn)
    • walk through them to find any matches: O(n^2)

total: O((n^2)log(n^2)) ( = O((n^2)log(n)) per comment from alestanis)

edit: i forgot about the distinct requirement, but that should not change the result.
first, to assure i!=j, just exclude i==j when building the list of all sums in step 1.
second, to assure i!=k and j!=k, tag each sum with its indices i,j, and tag each original value with its index k before sorting.
then in the last step when you find any match, check whether the tagged indices are distinct.

Upvotes: 1

alestanis
alestanis

Reputation: 21863

Yes there is.

First step: you sort the array.

Then you go through your indices in a smart way. A smart way could be to choose

  • a0 + a1
  • a0 + a2
  • a0 + a3
  • ...
  • a0 + a(n-1)
  • a1 + a(n-1)
  • a1 + a(n-2)

Smart here means that two consecutive pairs of tested indices must not be too far away from each other.

For the first one, aO + a1 you find if there is a k such that a0 + a1 = ak with binary search in O(logn).

For the following ones, given that the tested pair is close to the previous one, this means that if there is a k' such that ai + aj = ak' then k' must be close to k. You can probably get away with linear search from k until your k' matches or becomes too big/small for the ai + aj pair. This costs O(1) in the average case.

As you must tests n^2 pairs at most, the whole algorithm is O(n^2).

Upvotes: 2

Related Questions