Search for a specific sum of elements from two arrays

Question

Could you help me with this ?: "Let A and B be incrementally ordered arrays of natural numbers, and K be some arbitrary natural number. Find an efficient algorithm that determines all possible pairs of indices (i, j) for which A [i ] + B [j] = K Prove the correctness of the algorithm and evaluate its complexity.

Should I just iterate over the first array and do a binary search on the other? Thanks:)

Answer 1

No!

Both arrays are ordered, so you do the following:

• Put the itA iterator at the beginning of A
• Put the itB iterator at end B
• Moving iterators in opposite directions, testing *itA + *itB at each iteration. If the value is K , return both indexes. If the value is less than K , increment itA . Else, decrement itB .

When you go through both arrays, you do it in linear time.

Answer 2

Since for any A [i] there can be only one B [j], you can find a solution with complexity O (n + m). You can rely on the fact that if (A [i1] B [j1]) and (A [i2] B [i2]) are regular pairs and i1 is less than i2, then j1 must be greater than j2. Hope this helps.

Answer 3

I don't know if this helps, it's just an idea. Loop Linear and binary search B, but do A back. This may give you a better best case if you can exclude part B at every step in A.

If you know that A [i] needs to be told B [42] in order to solve for K, you will find out that A [i-1] is required at least B [43] or higher.

EDIT: I would also like to add that if B has fewer elements than A, rotate it and make B linearly.

Answer 4

A possible implementation in C ++ might look like this:

 #include <iostream> int main() { int A[]={1,2,3,6,7,8,9}; int B[]={0,2,4,5,6,7,8,12}; int K=9; int sizeB=sizeof B/sizeof(int); int sizeA=sizeof A/sizeof(int); int i=0; int j=sizeB-1; while(i<sizeA && j>=0) { if ((A[i]+B[j])==K){ std::cout << i<<","<<j<< std::endl; i++; j--; } else if((A[i]+B[j])<K){ i++; } else{ j--; } } return 0; }