The sum is a specific number. Is there any way to solve this problem in linear-time algorithm?
The sum is a specific number. Is there any way to solve this problem in linear-time algorithm?
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?
Thank you for replying. we do not know the location of two elements.
I need to add that there are n integers in each array, and each integer is between 0 and n^5.
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
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.Quote:
Originally Posted by bMorgan
kind regards,
Jos
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?
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.
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.Quote:
Originally Posted by bMorgan
To be more exact, the Map should be a Map<Integer, List<Integer>>
kind regards,
Jos