CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
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. ## 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?

3. Junior Member
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. ## 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?

#### Posting Permissions

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