Monday, January 23, 2012

Find Two Numbers in an Array that Sum to a Particular Value

We know that subset sum problem is np complete. But if we consider only subsets of size two, we can solve this problem in polynomial time.

Usually people tend to come up with n**2 solution. We can have a solution of order n if we use hashmaps

Algorithm

Iterate the array from i=0 to arraylength-1:
           if(hashMap does not contain key(sum - a[i]){
                insert ( a[i], sum[a-i])
           }
           else
           {
                return (a[i], sum-a[i])
            }

Logic:

After reading a value, check if its pair value (sum - a[i]) is already read.
If pair value is not read, insert the value read, and its pair value as key,value combination.
Otherwise return value and its pair value.