Find a pair of elements with given sum in the array

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

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