Problem name
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Problem name

  1. #1
    Join Date
    Aug 2011
    Posts
    1

    Problem name

    Hi, this is odd, i'm solving a problem but i don't know its name.

    The problem is the following:

    There are 2 (ordered) numbers array V and W.
    We have to find a number k which is the result of V[i]+W[j].

    There is a literature algorithm which solves it:

    i=0;
    j=size(W);

    while(true)

    If (V(i)+W(j)==k)
    return i,j;

    else if V(i)+W(j)>k
    j--;

    else if V(i)+W(j)<k
    i++


    Do you remember the name of the problem or the name of the algorithm?
    Thank you.

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,005

    Re: Problem name

    Seems kind of simple to be a named problem... Is there a reason you think it has a formal name?

    The 'literature' algorithm you cited is very simple. What is the source? Do they quote a name?
    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.

  3. #3
    Join Date
    Aug 2011
    Posts
    5

    Re: Problem name

    This problem is called, "given two sorted arrays A and B and an integer k, find the element in A and the element in B that sum to k".

    Only interesting problems get names. This one is not interesting.

    Also, the solution you gave is not the most efficient. If len(A) >= len(B), It is O(len(A)). If you do a binary search across A and B, you can reach the solution in O(log(len(A))) time.

  4. #4
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,005

    Re: Problem name

    Not sure I see the time complexity you state. Assume without loss of generality that len(A) >= len(B), then the algorithm is:

    Code:
    foreach b in B
        if k-b in A
            return a, b
    endfor
    
    otherwise return false
    Where if k-b in A can be done in O(log(A)) time by binary search. This gives a runtime complexity of O(B log(A)).

    By contrast, the algorithm given by AEmme has complexity O(A+B) ~ O(A), which is likely less.

    Agree? Or did I miss something?
    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.

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center