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];
}
Friday, September 2, 2011
Pair of indices such that A[i] 十A[j] =K in given Array
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment