Results 1 to 9 of 9
 02072011, 05:18 AM #1Member
 Join Date
 Nov 2010
 Posts
 9
 Rep Power
 0
 02072011, 05:21 AM #2Member
 Join Date
 Feb 2011
 Posts
 15
 Rep Power
 0
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?
 02072011, 06:30 AM #3Member
 Join Date
 Nov 2010
 Posts
 9
 Rep Power
 0
Thank you for replying. we do not know the location of two elements.
 02072011, 06:38 AM #4Member
 Join Date
 Nov 2010
 Posts
 9
 Rep Power
 0
I need to add that there are n integers in each array, and each integer is between 0 and n^5.
 02072011, 06:57 AM #5Member
 Join Date
 Feb 2011
 Posts
 15
 Rep Power
 0
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
 02072011, 07:14 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,524
 Blog Entries
 7
 Rep Power
 20
cenosillicaphobia: the fear for an empty beer glass
 02072011, 11:57 PM #7Member
 Join Date
 Nov 2010
 Posts
 9
 Rep Power
 0
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 lineartime algorithm solve this problem?
 02082011, 02:37 AM #8
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.
 02082011, 07:27 AM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,524
 Blog Entries
 7
 Rep Power
 20
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 zb[ j ] where z is the total you're looking for. If found b [ j ] + (z  b[ j ]) is the sum and the value zb[ 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,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

help w/ storing/scanning numbers in two dimensional arrays
By clemsontigers in forum New To JavaReplies: 15Last Post: 12022010, 02:08 AM 
help w/ storing/scanning numbers in arrays
By clemsontigers in forum New To JavaReplies: 15Last Post: 11182010, 05:12 AM 
Help with my code to find MinOfAll numbers
By May.ver.rick in forum New To JavaReplies: 9Last Post: 04202010, 04:46 AM 
Java program problem.. Arrays.. Random Numbers
By Chewart in forum New To JavaReplies: 16Last Post: 11162009, 10:21 PM 
Random numbers and arrays
By caro in forum New To JavaReplies: 6Last Post: 06102009, 01:09 AM
Bookmarks