Two numbers, x and y, are from two different arrays. Find if there is a sum z such that z= x+y

Question

I need to add that there are n integers in each array, and each integer is between 0 and n^5. Is there any way to solve this problem in linear-time algorithm?

This problem is addressed as a sub-problem of http://stackoverflow.com/q/3987264 — codaddict, Feb 07 '11 at 05:25
@codaddict: That problem would give a O(n*log(n)) solution, not O(n). (The first step was a sort.) — btilly, Feb 07 '11 at 05:32
The way the problem is stated, the solution would be "add them together." What exactly is the question here? — BlueRaja - Danny Pflughoeft, Feb 07 '11 at 05:41
The problem is still not clear ... do you have your `z` integers in a third array, or one specific given `z`? — Paŭlo Ebermann, Feb 07 '11 at 14:27

Mark Byers · Answer 1 · 2011-02-07T06:56:10.467

2

Yes it's possible in linear time under these assumptions:

Your inputs are arrays of (for example) 32-bit integers.
Adding two integers is an O(1) operation.
Your machine has unlimited memory and reading a byte anywhere in memory is an O(1) operation.

1) Convert one of the arrays into a hash set with approximately O(1) time complexity for lookups. Construction of the hash set takes approximately linear time.

2) Iterate over the other array and for each element i, check if x - i is in the hash set. If there is a match then (i, x - i) is a solution. This step requires linear time.

edited Feb 07 '11 at 06:56

answered Feb 07 '11 at 05:29

Mark Byers

811,555
193
1,581
1,452

That algorithm is O(n) average time, O(n*n) worst time. – btilly Feb 07 '11 at 05:58
@btilly: I've written the assumptions I'm using. – Mark Byers Feb 07 '11 at 06:56
You do not need to construct hash table, just two sorted arrays and index from one side going up and second index down. This way you can have provably linear time. Sorting takes also linear time because you know upper bound and you can use radix sort. – Luka Rahne Feb 07 '11 at 08:04
1

@ralu O(n * k), k still unknown and variable, radix sort is not linear for this case. – Pavan Yalamanchili Feb 07 '11 at 09:15

score 0 · Answer 2 · answered Feb 07 '11 at 05:29

I can not think of a linear time algorithm, but I can think of a O (m log n) solution where m is the length of the larger list and n is the length of the smaller list.

let n be the length of the smaller list and m be the length of the larger list.

Step 1: sort the smaller list (merge sort for example): O(n log n) Step 2: for each item in the larger list, try to find (target number - item) in the sorted list. If you find a match, you have found the two numbers you are looking for. O (m log n).

The complexity is O (n log n) + O (m log n) which is O (m log n) because m is the larger list.

Two numbers, x and y, are from two different arrays. Find if there is a sum z such that z= x+y

2 Answers2