Friday, September 2, 2011

Pair of indices such that A[i] 十A[j] =K in given Array

Design an efficient algorithm for determining if there exist
a pair of indices such that A[i] 十A[j] =K.

Normal way would cost us O(n^2) complexity. But using Hashing complexity reduces to O(n).
Second approach is to while parsing the array find the complement (K - arr[i]) . Store the array index in to a hash table. In the hash table we search for the complement. if the complement exist, it returns it.
sub pairsum(arr, K)
{
    H={}; // Hash array initialize to zero.
   for i in range(arr, len)
    complement = K - arr[i];
    H[arr[i]] = i; // Store the index of array element.
    if(H[complement])
      return H[complement], arr[i];
}

No comments:

Post a Comment