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

[bMorgan]

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

[Zepher]

Do you know the location of the two elements?

Would it be as simple as
int sum = arrayOne[1] + arrayTwo[1];

or something of the sort?

[bMorgan]

Thank you for replying. we do not know the location of two elements.

[bMorgan]

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

[Zepher]

I'm sorry but I don't think I understand exactly what you are trying to do....

If you have two arrays:
A[5] = [1,2,3,4,4]
B[5] = [4,5,6,3,2]

what are you trying to do? Ignoring the actual coding

[JosAH]

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

Do you want to find an element a[ i ] and b[ j ] from two arrays a and b where the sum of the two elements equals a value n? If so a simple quadratic algorithm can do the job; otherwise you have to elaborate on your problem a bit more.

kind regards,

Jos

[bMorgan]

Sorry, i should explain it. Find an element a[ i ] and b[ j ] from two arrays a and b where the sum of the two elements equals another number, like z. Can a linear-time algorithm solve this problem?

[quad64bit]

Without sorting the arrays first? Are the arrays unordered?
Think of it this way:
If you have two arrays, one with 5 elements, and one with 10 elements. In the worst case, if you need to find both numbers before summing them (though, if you don't know what they are, how are you going to search for them?), then in the worst case, you'll have to search 5 numbers in the first array, and 10 in the second. Thats linear (length of array A + length of array B).

But I think your problem is different. I think from reading your comments, that you know the sum, but not the two operands. You need to sum different values in the two arrays until you arrive at the right sum. Am I correct?

If this is the case, then the number of combinations is a permutation. If you take every element in array A and try adding them to every element in array B, in the best case you will have 2 reads, 1 add, and 1 comparison. Thats a scaler so it'd essentially be O(1). But in the worst case, you would have to compare every element in A to every element in B. Thats A*B operations. For every extra number in A or B, you will have to recheck every single number in the other array.

[JosAH]

Sorry, i should explain it. Find an element a[ i ] and b[ j ] from two arrays a and b where the sum of the two elements equals another number, like z. Can a linear-time algorithm solve this problem?

It can be done but you need a Map for that: stick all the values of array a in a Map as the key value; the index of the number is the associated value in the Map. This completes step 1 of the algorithm. Step 2 walks over array b and tries to find a value z-b[ j ] where z is the total you're looking for. If found b [ j ] + (z - b[ j ]) is the sum and the value z-b[ j ] in the map tells you where you can find that number in array a.

To be more exact, the Map should be a Map<Integer, List<Integer>>

kind regards,

Jos