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