Question

Design an O(n log n) 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

CODE:

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

// function to search 'value' in the given array 'arr[]' it uses binary search technique as 'arr[]' is sorted
int isPresent(int arr[], int low, int high, int value)
{
   while (low <= high)
   {
       int mid = (low + high) / 2;
      
       // value found
       if (arr[mid] == value)
           return mid;     
          
       else if (arr[mid] > value)
           high = mid - 1;
       else
           low = mid + 1;
   }
  
   // value not found
   return -1;
}

// function to find pair from both the sorted arrays whose sum is equal to a given value
void Pairs(int arr1[], int arr2[], int m, int n, int x)
{
   int count = 0;     
   for (int i = 0; i < m; i++)
   {
       // for each arr1[i]
       int value = x - arr1[i];
      
       // check if the 'value' is present in 'arr2[]'
   int j = isPresent(arr2, 0, n - 1, value);
       if (j != -1)
           cout << i << " " << j << endl;
   }
}

// Driver Code
int main()
{
   int arr1[] = {1, 3, 5, 7};
   int arr2[] = {2, 3, 5, 8};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   int x = 10;
   Pairs(arr1, arr2, m, n, x);
   return 0;     
}

Method (Binary Search): For each element arr1[i], where 1 <= i <= m, search the value (x – arr1[i]) in arr2[]. If search is successful, increment the count.

Time Complexity: O(mlogn). Binary search time complexity: O(log n). So, for m elements time complexity is: O(mlogn)