CODEWITHSUNDEEP
javaalgorithmsearchbig-o
Maklee Lee
Maklee Lee

Reputation: 283

How to find two number whose sum is given number in sorted array in O(n)?

public static void findNumber(int number) {
    int[] soretedArray = { 1, 5, 6, 8, 9 };
    for (int i = 0; i <= soretedArray.length; i++) {
        for (int j = i + 1; j < soretedArray.length; j++) {
            if (soretedArray[i] + soretedArray[j] == number) {
                System.out.println(soretedArray[i] + "::" + soretedArray[j]);
                return;
            }
        }
    }
}

Using this code I am able to find the number and its complexity is O(N^2) but I have to find this using O(N) complexity i.e using only one for loop or hash-map or similar in Java.

Upvotes: 5

Views: 994

Answers (3)

Anonymous
Anonymous

Reputation: 86232

As explained in the Google video that Alexander G is linking to, use two array indexes. Initialize one to the first element (0) and the other to the last element (sortedArray.length - 1). In a loop, check the sum of the two elements at the two indexes. If the sum is the number you were looking for, you’re done. If it’s too high, you need to find a smaller number at one of the indexes; move the right index one step to the left (since the array is sorted, this is the right way). If on the other hand, the sum you got was too low, move the left index to the right to obtain a higher first addend. When the two indexes meet, if you still haven’t found the sum you were looking for, there isn’t any. At this point you have been n - 1 times through the loop, so the algorithm runs in O(n).

We ought to first check the precondition, that the array is really sorted. This too can be done in O(n), so doing it doesn’t break any requirements.

The algorithm may need refinement if you are required to find all possible pairs of numbers that yield the desired sum rather than just one pair.

Is this answer superfluous when the video link has already said it? For one thing, my explanation is shorter, so if it suffices, you’re fine. Most importantly, if the video is removed or just moved to another URL, my answer will still be here.

Upvotes: 2

Aleksandar G
Aleksandar G

Reputation: 1181

I remember, I was watching the official Google video about this problem. Although it is not demonstrated in java, it is explained step-by-step in different variations of the problem. You should definitely check it:

How to: Work at Google — Example Coding/Engineering Interview

Upvotes: 2

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36391

With fixed number, for any chosen x in the array you just have to find if number-x is in the array (Note that you can also bound x). This will not give you O(n), but O(n.log(n)).

Maybe by remarking that if you have a_i and a_j (j>i), taking the sum and comparing against number, if the result is greater next interesting tests are with a_(i-1) or a_(j-1), and if result is lower next interesting tests are with a_(i+1) or a_(j+1), will give hint to linear-time?

Upvotes: 1

Related Questions