## 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;

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

if(curSum == sum)
{
*num1 = data[behind];
found = true;
break;
}
else if(curSum > sum)
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;

{
if(behind == excludeIndex)
behind ++;

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

if(curSum == sum)
{
found = true;
break;
}
else if(curSum > sum)
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.

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

1. Hi Harry,

This is indeed great! But I think perhaps you are generally referring No. 09 - Numbers with a Given Sum which is getting unsustainable.

I have a custom application which I share with the customer as private AMI. However, I want to make sure the customer have accepted the license terms before launching the AMI. I don't see a option or a way to prompt the end user with license agreement (EULA) when they launch EC2 instance.

Configuration management has been around for a long time in web operations and systems administration. Yet the cultural popularity of it has been limited AWS Training . Most systems administrators configure machines as the software was developed before version control – that is manually making changes on servers.

Very useful article, if I run into challenges along the way, I will share them here.

Ciao,
Kevin

2. Great Article IoT Projects for Students

Deep Learning Projects for Final Year

JavaScript Training in Chennai

JavaScript Training in Chennai

The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

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

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

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

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

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

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.

1. insert n elements into hashtable takes nlogn time

2. insert n elements into a hashtable takes n time

5. nlgn is possible

6. Ha, I just interviewed this question by facebook.

7. 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:

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

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.

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

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

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

10. 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

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

12. This comment has been removed by the author.

13. 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

14. Hello,

A really interesting, clear and easily readable No. 09 - Numbers with a Given Sum article of interesting and different perspectives .I will clap. So much is so well covered here.

However, when .ebignore is present in yout project directory, the EB CLI doesn't use git commands and semantics to create your source bundle. This means that EB CLI ignores files specified in .ebignore, and includes all other files. In particular, it includes uncommitted source files.

Anyways great write up, your efforts are much appreciated.

Grazie,
Irene Hynes

15. Hello Mate,

Grazie! Grazie! Grazie! Your blog is indeed quite interesting around Numbers with a Given Sum I agree with you on lot of points!

There wouldn't be any static charges such as monthly fee for setting up a static website beyond the resources that you are expecting to use. AWS Training The Simple Monthly Calculator in this case would be dependent on the expected Data Transfer, S3 usage and Route 53 config usage

Follow my new blog if you interested in just tag along me in any social media platforms!

Thank you,

16. 17. agen sabung ayam filipins128 terpercaya

18. 19. Bosan Menang tidak dibayar ? judi sabung ayam

20. 21. 22. 23. 