Find two elements in an array whose sum is x

Given an array of integers and a number x. check if there exists two elements in the array whose sum = x.

For every element arr[i] of the array, we need to check if the array contains (x-arr[i]) in it or not. This search for (x-arr[i]) can be made using linear search (O(n) -time algorithm), Binary Search(O(lg(n)) – time algorithm) or Hashing (O(1) – time look-up algorithm).
The 3 methods below uses these three searches only.
Brute-Force Method (Linear Search):

For ever element in the array check (linearly) if there exist another element such that the sum is x.

void findPair(int * arr, int n)
{
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
            if(arr[i]+arr[j] == x)
            {
                printf("Pair exist at index %d and %d", i, j);
            }
    printf("Pair does not exist");
}

Time Complexity: O(n²)
Extra Space: O(1)

Sorting the Array:

Basically for every element arr[i] we need to find (x-arr[i]) in the remaining array.

The problem in the first method is that we are searching for that element (x-arr[i]) in array using linear search. This method uses Binary search to search in the array and hence is better than the previous one. But Binary search is only applicable on the sorted array.

1. Sort the Array.
2. For every element arr[i]
    Search (x-arr[i]) in the array arr[i .. n-1] using Binary Search
       If FOUND return true
       Else return false

Time Complexity: O(n.lg(n)) – Time taken to sort the array
Extra Space: O(1) – May change if the sorting algorithm is taking auxiliary space

Using Hashing:

This is most applicable when range of numbers in the array is small and known. Else the hash-table implementation will be complicated and the gain in the execution time is probably not worth it.

1. Initialize the hash-map
2. For each element in the array
   Check if (x-arr[i]) is present in the Hash
      If present, The pair exist
      Else, No such pair exist

Code:

Below is the complete code with all the three options.

//
//Created by Kamal Rawat.
//Copyright © 2018 Ritambhara Technologies. All rights reserved.
//
#include
#include

using namespace std;
bool binarySearch(int *arr, int n, int x, int excludeIdx)
{
  int low = 0; int high = n-1;
  while(low <= high)
  {
    int mid = (low+high)/2;
    if(mid == excludeIdx)
    {
      if ( (mid0 && arr[mid-1]==x) )
        return true;
      else
        return false;
    }
    if(arr[mid] == x)
      return true;
    else if(arr[mid] > x)
      high = mid-1;
    else
      low = mid+1;
  }
  return false;
}
bool linearSearch(int *arr, int n, int x)
{
  for(int i=0; i<n; i++)
    if(arr[i] == x)
      return true;
  return false;
}
// LINEAR SEARCH SOLUTION
bool findPairWithSum1(int* arr, int n, int x)
{
  for(int i=0; i<n-1; i++)
  {
    if(linearSearch(arr+i+1, n-i-1, x-arr[i]))
      return true;
  }
  return false;
}
// BINARY SEARCH SOLUTION
bool findPairWithSum2(int* arr, int n, int x)
{
  for(int i=0; i<n-1; i++)
  {
    if(binarySearch(arr, n, x-arr[i], i))
      return true;
  }
  return false;
}
// HASHMAP SOLUTION
bool findPairWithSum3(int* arr, int n, int x)
{
  // CREATE THE HASHMAP
  map<int, int> hash;
  // INSERTING INTO THE HASHMAP
  for(int i=0; i<n-1; i++)
    hash.insert(std::pair<int, int>(arr[i],1));
  //SEARCHING IN THE HASHMAP
  for(int i=0; i<n-1; i++)
  {
    if(hash.find(x-arr[i]) != hash.end())
      return true;
  }
  return false;
}
int main()
{
  int arr[] = { 2, 9, 7, 4, 5, 1, 0, 8};
  cout<<findPairWithSum1(arr, 8, 15);
  return 0;
}

Time Complexity: O(n)
Extra Space: O(n) – May be less if the range of numbers is less (repeating numbers).

DATABASE FOR PLACEMENT PREPARATION. PART_2

Find Merge-Point of two Linked Lists

Find two elements in an array whose sum is x

Leave a Reply Cancel reply