Find the sum of two numbers that are from two different arrays.
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Find the sum of two numbers that are from two different arrays.

1. Junior Member
Join Date
Feb 2011
Posts
4

## Find the sum of two numbers that are from two different arrays.

The sum is a specific number. Is there any way to solve this problem in linear-time algorithm?

2. ## Re: Find the sum of two numbers that are from two different arrays.

Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

Are the arrays sorted ?

Regards,
Zachm

3. Junior Member
Join Date
Feb 2011
Posts
4

## Re: Find the sum of two numbers that are from two different arrays.

I need to add that there are n integers in each array, and each integer is between 0 and n^5.

4. Junior Member
Join Date
Feb 2011
Posts
4

## Re: Find the sum of two numbers that are from two different arrays.

Originally Posted by Zachm
Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

Are the arrays sorted ?

Regards,
Zachm
Yes.

5. Junior Member
Join Date
Feb 2011
Posts
4

## Re: Find the sum of two numbers that are from two different arrays.

but the arrays are not sorted

6. ## Re: Find the sum of two numbers that are from two different arrays.

If they're sorted, the algorithm should be obvious.

If they're not sorted, you can't sort (and use the obvious algorithm then) them because that will cost O(n log n) which is supralinear, so you'll need to do something tricky...

This looks like a homework question so I will refrain from just posting the answer. Basically the problem is that you need an efficient way to check if the difference S-X[i] is in array Y. I implemented a way of doing this just to measure the time it takes to solve 1000 of these and got these results:

Code:
```       n    Time in seconds
10    0.01
20    0.005
40    0.01
80    0.016
160    0.039
320    0.067
640    0.117
1280    0.306
2560    0.768
5120    1.064
10240    2.369
20480    5.167
40960    14.517```
This looks pretty linear to me, although the pattern of residuals hints that it might actually be exponential. I suspect this might be due to the time spent allocating one of the data structures. Not sure...

When I modified the search routine to use a constant-size data structure (and so avoid differences in their allocation speed), I lost any clear dependence on size, so... dunno. Those benchmarks don't seem very informative.

So short answer: yes, I think you can, but I'm not really sure.

I should note that I modified the problem to facilitate computation. Values range between 0 and n^2 instead of n^5. I don't see how this affects algorithmic time complexity, however.
Last edited by BioPhysEngr; February 7th, 2011 at 02:50 AM. Reason: increase clarity

7. ## Re: Find the sum of two numbers that are from two different arrays.

Eh, maybe the n^5 thing does matter. My find match subroutine returns as soon as any match is found. The probability of finding a match is probably dependent on the size of the array (and the numbers that can be contained within)...

8. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Find the sum of two numbers that are from two different arrays.

---

9. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Find the sum of two numbers that are from two different arrays.

I suppose you are seeking an avarage-case algorithm complexity, so...

drop all the array elements greater then your input number and answer the following question : what's the avarage size of the resulting reduced arrays with respect to n ?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•