Question

Design an O(nlogn) algorithm that takes two arrays A and B (not necessarily sorted) of size n of real numbers and a value v. The algorithm returns i and j if there exist i and j such that A[i] + B[j] = v and no otherwise. Describe your algorithm in English and give its time analysis.

Answer 1

Algorithm -

Step 1: Sort both the arrays A and B.

Step 2: Set i = 1 and j = n (Assuming array indices are from 1 to n)

Step 3: If i<=j, proceed to Step 4. Otherwise, return that no such i,j exist and terminate the algorithm.

Step 4: If A[i] + B[j] = v, then we have found i,j as needed. We can return i and j as the result and terminate the algorithm.

If A[i] + B[j] < v, then increment i by 1.

If A[i] + B[j] > v, then decrement j by 1.

Step 5: Goto Step 3.

Time Complexity -

We can sort both the arrays A and B in O( n log n ) time. (Step 1)

The loop will run for a maximum n times in the worst case. So, it will take O( n ) time.

Hence, the overall time taken is O ( n + n log n ) which is O( n log n ).

C++ Code -

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
   int n,v;
   cout<<"Enter array size\n";
   cin>>n;
   vector<int> A(n);
   vector<int> B(n);
   int k;
   cout<<"Enter "<<n<<" values for array A(seperated by space)\n";
   for(k=0;k<n;k++)
       cin>>A[k];
   cout<<"Enter "<<n<<" values for array B(seperated by space)\n";
   for(k=0;k<n;k++)
       cin>>B[k];
   sort(A.begin(),A.end());
   sort(B.begin(),B.end());
   cout<<"Enter value of v\n";
   cin>>v;
   int i = 0, j = n-1;
   while(i<=j) {
       if(A[i]+B[j]==v) {
           cout<<"i and j exist such that A[i]+B[j]=v"<<" --> i = "<<i<<" j = "<<j<<endl;
           return 0;
       }
       else if(A[i]+B[j]<v)
           i++;
       else
           j--;
   }
   cout<<"No such i and j exist such that A[i]+B[j]=v\n";
   return 0;
}