How to find 2 numbers and their sum in an unsorted array

Question

This was an interview question that I was asked to solve: Given an unsorted array, find out 2 numbers and their sum in the array. (That is, find three numbers in the array such that one is the sum of the other two.) Please note, I have seen question about the finding 2 numbers when the sum (int k) is given. However, this question expect you to find out the numbers and the sum in the array. Can it be solved in O(n), O(log n) or O(nlogn)

There is a standard solution of going through each integer and then doing a binary search on it. Is there a better solution?

public static void findNumsAndSum(int[] l) {
    // sort the array
    if (l == null || l.length < 2) {
        return;
    }
    BinarySearch bs = new BinarySearch();
    for (int i = 0; i < l.length; i++) {
        for (int j = 1; j < l.length; j++) {
            int sum = l[i] + l[j];
            if (l[l.length - 1] < sum) {
                continue;
            }
            if (bs.binarySearch(l, sum, j + 1, l.length)) {
                System.out.println("Found the sum: " + l[i] + "+" + l[j]
                        + "=" + sum);
            }
        }
    }
}

if `k` is not given, then... what's the task? I don't get it... could you give an example (input + expected output) ? — Karoly Horvath, Aug 02 '12 at 23:54
The task is to find three numbers in the array such that one of the three numbers is the sum of the other two. — Eric Postpischil, Aug 03 '12 at 00:09

score 4 · Answer 1 · answered Jul 29 '12 at 01:01

This is very similar to the standard problem 3SUM, which many of the related questions along the right are about.

Your solution is O(n^2 lg n); there are O(n^2) algorithms based on sorting the array, which work with slight modification for this variant. The best known lower bound is O(n lg n) (because you can use it to perform a comparison sort, if you're clever about it). If you can find a subquadratic algorithm or a tighter lower bound, you'll get some publications out of it. :)

Note that if you're willing to bound the integers to fall in the range [-u, u], there's a solution for the a + b + c = 0 problem in time O(n + u lg u) using the Fast Fourier Transform. It's not immediately obvious to me how to adjust it to the a + b = c problem, though.

We can assume that the number are positive numbers. I still fail to see how we can achieve O(n lg n) — masti, Jul 29 '12 at 01:15
@masti See [my answer here](http://stackoverflow.com/a/10304196/344821) for most of the solution, though it doesn't quite get all the way there. — Danica, Jul 29 '12 at 01:22

Lukas Häfliger · Answer 2 · 2012-08-03T00:02:01.933

You can solve it in O(nlog(n)) as follows:

Sort your array in O(nlog(n)) ascendingly. You need 2 indices pointing to the left/right end of your array. Lets's call them i and j, i being the left one and j the right one.

Now calculate the sum of array[i] + array[j].

If this sum is greater than k, reduce j by one.
If this sum is smaller than k. increase i by one.

Repeat until the sum equals k.

So with this algorithm you can find the solution in O(nlog(n)) and it is pretty simple to implement

Sorry. It seems that I didn't read your post carefully enough ;)

How to find 2 numbers and their sum in an unsorted array

2 Answers2