Thursday, October 20, 2011

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 {12471115}

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(n2) time in the for loop. Therefore, its overall time complexity is O(n2).

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.

20 comments:

  1. What if the numbers of the array in the first question are not sorted ??

    ReplyDelete
  2. When numbers are not sorted, we have sort them firstly.

    ReplyDelete
    Replies
    1. Is any better way than O(n^2)? I haven't figure it out.

      Delete
    2. It would be O(nlogn) because that's how long it takes to sort.

      Delete
    3. If it is unsorted the order will still be n^2. Because, O(nlogn + n^2)=O(n^2)

      Delete
  3. can we find all the pairs whose sum < x in o(n) ??

    ReplyDelete
  4. @Harry:
    In the first case if the numbers are not sorted we can still do it in O(n) but we also need O(n) space. Get a set containing numbers (target - number[i]) and then scan the array again to see if it contains number[i]. If there can be duplicated you need to change the set to a map.

    ReplyDelete
    Replies
    1. insert n elements into hashtable takes nlogn time

      Delete
    2. insert n elements into a hashtable takes n time

      Delete
  5. Ha, I just interviewed this question by facebook.

    ReplyDelete
  6. I think a more intuitive way of doing Problem 2 would be 3 nested for loops.

    This is the code in Python that explains my idea:

    def facebook(array):
    if len(array) < 3:
    return False;
    else:
    for i in range(0, len(array) - 2):
    for j in range(1, len(array) - 1):
    for k in range(2, len(array)):
    if array[i] + array[j] + array [k] == 0:
    return True

    return False

    ReplyDelete
    Replies
    1. This solution in not correct, and it costs O(n^3) time. It is not correct because it is possible for i=j=k, so you might be counting the same entry more than once.

      Delete
  7. About the method [FindNumbersWithSum] in problem2, I think we can initiate behind = excludeIndex + 1, instead of 0;

    ReplyDelete
  8. For Problem 1, We need to short the array (nlogn). how could be your complexity is O(n)

    ReplyDelete
    Replies
    1. We only need to scan the array once, so the complexity is O(n).

      Delete
  9. From the sorted array, take an element Xn one by one. The problem becomes searching for another number (S-Xn) in the array. Overall, complexity is O(nlogn), but it gives all the pairs

    ReplyDelete
  10. here a O(n) solution: http://ideone.com/bfSkv1

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. Problem 2 can be optimized further.

    First time through the for loop, we call FindNumbersWithSum
    with excludeIndx = 0. If we cannot find a pair, it means
    that the number with index 0 will never be in the final soln.

    Second time through the for loop, we call FindNumbersWithSum
    with excludIdx = 1. Here we should be excluding all indices
    <= 1, instead of just excluding 1.

    The time complexity will still be O(n^2) though

    ReplyDelete