CODEWITHSUNDEEP
arraysalgorithmsearchbinary
user1772639
user1772639

Reputation: 43

Finding a specific sum of elements from two arrays

Could you please help me with this one? : "Let A and B are an incrementally ordered arrays of natural numbers and K be some arbitrary natural number. Find an effective algorithm which determines all possible pairs of indexes (i,j) such that A[i]+B[j]=K. Prove algorithm's correctness and estimate its complexity."

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

Upvotes: 4

Views: 289

Answers (4)

andilabs
andilabs

Reputation: 23281

Possible implementation in C++ can look as follows:

#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;
}

Upvotes: 0

AntonNiklasson
AntonNiklasson

Reputation: 1749

I don't know if it helps, it's just an idea. Loop A linearly and binary search B, but do A backwards. This might give you a better best case, by being able to exclude some portion of B at each step in A.

If you know that A[i] needed say B[42] to solve for K, you'll know that A[i-1] will need at least B[43] or higher.

EDIT: I would also like to add that if B has fewer elements than A, turn it around and do B linearly instead.

Upvotes: 0

Azad Salahli
Azad Salahli

Reputation: 916

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

Upvotes: 1

alestanis
alestanis

Reputation: 21863

No!

Both arrays are ordered, so you do the following:

  • Place an iterator itA on the beginning of A
  • Place an iterator itB on the end of B
  • Move iterators in opposite directions, testing *itA + *itB at each iteration. If the value is equal to K, return both indexes. If the value is smaller than K, increment itA. Else, decrement itB.

When you go through both arrays, you are done, in linear time.

Upvotes: 6

Related Questions