Finding two numbers in a sorted array satisfying a condition say x+y = 40

This is another interesting problem which has more than one solution. The problem definition says given numbers e.g. 3, 5,8,23,35,54,67 find two numbers x and y such that x+y = 40. Of course numbers can be negative too but should be integers only. The other specification is that the numbers are in sorted order.

The first solution that comes to mind is: Pick the first number, keep on comparing it with each of the remaining numbers in the array one by one. Then repeat this for the second, third and up to the last number.

If such a pair exists (x+y=40) we are guaranteed to find it. If not we will know for sure. What is the complexity of doing this?

For size n we run n-1 elements, for n-1 we run n-2 elements. So basically this turns out to be O(n)^2 or polynomial of order two. Logically speaking we need to compare every single number with every other number present in the array.

We sure can have a better solution. The above would work even if the array is not sorted. Can we take advantage of that?

Sure we can: Pick a number. Suppose that is x, now to see if y exists in the array, simple mathematics tells us

y = 40-x

So for e.g. when we picked the first number x=3, then it can only be x (or y) if 37 (40-3) exists in the array. How can we find a single number in an array efficiently?

Binary search is the answer! Basic algorithm is – Given a sorted array, divide it into two halves. If the number you are looking for is less than the half, then it sure can’t exist in the latter half and will only be present in the first half. If greater than half you can ignore the first half. Then divide the remaining array again into half and repeat the process. This way if number exists, we would find it in lg(n), because we are diving the array into two every time so eliminating half elements per iteration.

So in the original problem x+y = 40, we iterate through the whole array picking one element as x at a time and applying binary search to find y in lg n. This results into entire complexity of n.lg(n) which is much better than n^2. Code would follow:

#include <iostream>
#include <cmath>
using namespace std;

#define MAX_SIZE    8

/* Function takes array to be searched in, number to search for as arguments and    
 * returns the index of number if found in array. It would return -1 otherwise.
 */
int bin_search(int arr[], int size, int num_to_search);

int main()
{
    int arr[MAX_SIZE] = {2,5,8,17,23,47,54,67};

    for (int out_ctr=0; out_ctr < MAX_SIZE; out_ctr++)
    {
        int x = arr[out_ctr];
        int y = 40 - x;

        int index = bin_search(arr, MAX_SIZE, y);

        if(index != -1) {
            printf("y found at index %d - so %d + %d = 48 exist\n", index, x, y);
            break; // we are only looking for one satisfactory pair
        }

        else
            printf("Not found yet - so %d can't be x - Look for more\n", x);

    }
    return 0;
}

int bin_search(int arr[], int size, int num_to_search)
{
    int index_of_num = -1;
    int left=0, right=size-1;
    int middle;

    while(left <= right)
    {
        middle = (left+right) / 2;

        if(arr[middle] == num_to_search)
        {
            index_of_num = middle;
            break;
        }

        else if(arr[middle] < num_to_search)
        {
            left = middle + 1;
        }

        else // (arr[middle] > num_to_search)
        {
            right = middle - 1;
        }
    }

    return index_of_num;
}

But wait! Is this the fastest possible solution? This is the part that is making it an advanced tutorial:

Can we improve on nlg(n)? For this specific problem the answer is – yes. It can be done in O(n).

Hint – We only need ONE such pair satisfying x+y = 40, not all (possible) pairs:

How? The idea is you keep two indexes one low and other high (0 and MAX_SIZE – 1). Now if the sum is lesser than the required sum, increment low by one index. But if the sum is greater than the required value, decrement high by one index. Code follows (only one for loop):

for(int low=0, high=MAX_SIZE-1; low <=high;)
    {
        int curr_sum = arr[low] + arr[high];

        if( curr_sum < 40)
            low++;
        else if( curr_sum > 40)
            high--;
        else // both are equal
        {
            printf("low indx %d - high indx %d :%d+%d=40 exist\n", low, high, arr[low], arr[high]);
            break;
        }
    }

The above code runs in O(n). Though I would say it is hard to come up with on initial attempts. However, any decent programmer should be able to do at least the nlg(n) solution using binary search.

Edited by Alexander, 07 May 2011 - 01:28 AM.
Code formatting

for(int low=0, high=MAX_SIZE-1, curr_sum; low < high; curr_sum < 40 ? ++low : --high) { if((curr_sum = arr[low] + arr[high]) == 40) { printf("low indx %d - high indx %d :%d+%d=40 exist\n", low, high, arr[low], arr[high]); break; } }

Thank you Zeke Dragon - That sure is a good deal of compression.

I would like to mention a small personal experience. I started doing this too, went beyond moderate level and one day a friend of mine showed me the site and prize listings of "most obfuscated codes" :)

So i realized it is hard to keep the balance, and have subconsciously started writing very simple code.

Having said that, the above change is still pretty simple (not obfuscated at all - but i was just voicing my thoughts as i have dropped using conditional op at all as a personal choice) and i am glad i can find audience who reads and enjoys playing around with code.

I look forward to having more fun playing around with code.

Pardon me, but what exactly is +rep? I thought it is some site specific thing such as Likes, but i couldn't find it.