# Interview Questions

# Find two elements in an array whose sum is x

- August 8, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

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^{2})

**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:**

Let all the elements in the array be in the Range from 0 to RANGE

#define RANGE 10 void checkPairs(int *arr, int n, int x) { int hash[RANGE] = {0}; // Populating the Hash-Map for(int i=0; i<n; i++) hash[arr[i]]++; for(int i=0; i<n; i++) if( x-arr[i]>=0 && hash[x-arr[i]]>=1) printf("Pair Exist"); }

**Time Complexity:** O(n)

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