Aug 082012
 

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(n2)
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).

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)