CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9
  1. #1
    Join Date
    Feb 2011
    Posts
    4

    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
    Join Date
    Oct 2006
    Posts
    616

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

    Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

    Are the arrays sorted ?

    Regards,
    Zachm

  3. #3
    Join Date
    Feb 2011
    Posts
    4

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

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

  4. #4
    Join Date
    Feb 2011
    Posts
    4

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

    Quote Originally Posted by Zachm View Post
    Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

    Are the arrays sorted ?

    Regards,
    Zachm
    Yes.

  5. #5
    Join Date
    Feb 2011
    Posts
    4

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

    but the arrays are not sorted

  6. #6
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

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

    If they're sorted, the algorithm should be obvious.

    If they're not sorted, you can't sort (and use the obvious algorithm then) them because that will cost O(n log n) which is supralinear, so you'll need to do something tricky...

    This looks like a homework question so I will refrain from just posting the answer. Basically the problem is that you need an efficient way to check if the difference S-X[i] is in array Y. I implemented a way of doing this just to measure the time it takes to solve 1000 of these and got these results:

    Code:
           n    Time in seconds
          10    0.01
          20    0.005
          40    0.01
          80    0.016
         160    0.039
         320    0.067
         640    0.117
        1280    0.306
        2560    0.768
        5120    1.064
       10240    2.369
       20480    5.167
       40960    14.517
    This looks pretty linear to me, although the pattern of residuals hints that it might actually be exponential. I suspect this might be due to the time spent allocating one of the data structures. Not sure...

    When I modified the search routine to use a constant-size data structure (and so avoid differences in their allocation speed), I lost any clear dependence on size, so... dunno. Those benchmarks don't seem very informative.

    So short answer: yes, I think you can, but I'm not really sure.

    I should note that I modified the problem to facilitate computation. Values range between 0 and n^2 instead of n^5. I don't see how this affects algorithmic time complexity, however.
    Last edited by BioPhysEngr; February 7th, 2011 at 03:50 AM. Reason: increase clarity
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  7. #7
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

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

    Eh, maybe the n^5 thing does matter. My find match subroutine returns as soon as any match is found. The probability of finding a match is probably dependent on the size of the array (and the numbers that can be contained within)...
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    May 2009
    Posts
    2,413

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

    ---

  9. #9
    Join Date
    Oct 2008
    Posts
    1,456

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

    I suppose you are seeking an avarage-case algorithm complexity, so...

    drop all the array elements greater then your input number and answer the following question : what's the avarage size of the resulting reduced arrays with respect to n ?

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured