No. 09 - Numbers with a Given Sum

Problem 1: Given an increasingly sorted array and a number s, please find two numbers whose sum is s. If there are multiple pairs with sum s, just output any one of them.

For example, if the inputs are an array {1, 2, 4, 7, 11, 15} and a number 15, please out two numbers 4 and 11 since 4+11=15.

Analysis: Let us firstly have a try to select two numbers (denoted as num1 and num2) of the input array. If their sum equals to s, we are fortunate because the required numbers have been found. If the sum is less than s, we may replace num1 with its next number, because the array is increasingly sorted and its next number should be greater. If the sum is greater than s, num2 can be replaced with its previous number in the sorted array, which should be less than num2.

Take the array {1, 2, 4, 7, 11, 15} and number 15 as an example. We define two pointers. At the first step, they point to the first number (also the least one) 1 and the last number (also the greatest one) 15. We move the second pointer forward to number 11, since their sum 16 and it is greater than 15.

At the second step, the two numbers are 1 and 11, and their sum 12 is less than 15. Therefore, we can move the first pointer afterward and let it point to 2.

The two numbers are 2 and 11 accordingly at the third step. Since their sum 13 is less than 15, we move the first pointer afterward again.

Now the two numbers are 4 and 11, and their sum is 15 which is the expected sum. Therefore, we have found two numbers whose sum is 15.

The process is summarized as in Table 1:

Step	Num1	Num2	Sum	Comparing with s	Operation
1	1	15	16	Greater	Select the previous number of Num2
2	1	11	12	Less	Select the next number of Num1
3	2	11	13	Less	Select the next number of Num1
4	4	11	15	Equal

Table 1: Find a pair of numbers with sum 15 out of array {1、2、4、7、11、15}

After interviewers approve our solution, we can begin to write code. The following is a piece of sample code:

bool FindNumbersWithSum(int data[], int length, int sum,

                        int* num1, int* num2)

{

    bool found = false;

    if(length < 1 || num1 == NULL || num2 == NULL)

        return found;

    int ahead = length - 1;

    int behind = 0;

    while(ahead > behind)

    {

        long long curSum = data[ahead] + data[behind];

        if(curSum == sum)

        {

            *num1 = data[behind];

            *num2 = data[ahead];

            found = true;

            break;

        }

        else if(curSum > sum)

            ahead --;

        else

            behind ++;

    }

    return found;

}

In the code above, ahead is the index of the first number, and behind is the index of the second number. Since we only need to scan the input array once, its time complexity is O(n).

Problem 2: Given an array, please determine whether it contains three numbers whose sum equals to 0.

Analysis: This problem is also required to find some numbers with a given array and sum, it is similar to the first problem. We may get some hints from the solution above.

Since the input of the previous problem is an increasingly sorted array, we can also firstly sort the input array increasingly. Secondly we scan the array. When we reach the i-th number with value n, we try to find whether there are two numbers whose sum is –n in the array excluding the i-th number.

It is time for us to write some code. We modify the function FindNumbersWithSum above a little bit:

bool FindNumbersWithSum(int data[], int length, int sum, int excludeIndex)

{

    bool found = false;

    int ahead = length - 1;

    int behind = 0;

    while(ahead > behind)

    {

        if(ahead == excludeIndex)

            ahead --;

        if(behind == excludeIndex)

            behind ++;

        long long curSum = data[ahead] + data[behind];

        if(curSum == sum)

        {

            found = true;

            break;

        }

        else if(curSum > sum)

            ahead --;

        else

            behind ++;

    }

    return found;

}

It determines whether there are two numbers whose sum is sum in array data excluding the number with index excludeIndex. We can determine whether there are three numbers in an array with sum 0 based on this function:

bool HasThreeNumbersWithSum0(int data[], int length)

{

    bool found = false;

    if(data == NULL || length < 3)

        return found;

    std::sort(data, data + length - 1);

    for(int i = 0; i < length; ++i)

    {

        int sum = -data[i];

        int num1, num2;

        found = FindNumbersWithSum(data, length, sum, i);

        if(found)

            break;

    }

    return found;

}

It contains two steps in function HasThreeNumbersWithSum0. It costs O(nlogn)time to sort n numbers at its first step. At its second step it costs O(n) time for each number to call FindNumberWithSum, so it costs O(n²) time in the for loop. Therefore, its overall time complexity is O(n²).

The discussion about these two problems is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.