Results 1 to 9 of 9
  1. #1
    bMorgan is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default 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. #2
    Zepher is offline Member
    Join Date
    Feb 2011
    Posts
    15
    Rep Power
    0

    Default

    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?

  3. #3
    bMorgan is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default

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

  4. #4
    bMorgan is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default

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

  5. #5
    Zepher is offline Member
    Join Date
    Feb 2011
    Posts
    15
    Rep Power
    0

    Default

    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

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by bMorgan View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    bMorgan is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default

    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?

  8. #8
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by bMorgan View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. help w/ storing/scanning numbers in two dimensional arrays
    By clemsontigers in forum New To Java
    Replies: 15
    Last Post: 12-02-2010, 02:08 AM
  2. help w/ storing/scanning numbers in arrays
    By clemsontigers in forum New To Java
    Replies: 15
    Last Post: 11-18-2010, 05:12 AM
  3. Help with my code to find MinOfAll numbers
    By May.ver.rick in forum New To Java
    Replies: 9
    Last Post: 04-20-2010, 04:46 AM
  4. Java program problem.. Arrays.. Random Numbers
    By Chewart in forum New To Java
    Replies: 16
    Last Post: 11-16-2009, 10:21 PM
  5. Random numbers and arrays
    By caro in forum New To Java
    Replies: 6
    Last Post: 06-10-2009, 01:09 AM

Posting Permissions

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