Wednesday, September 13, 2017

Finding two items in array that has sum of s

Suppose we have an array A with n items (A[0]...A[n-1]) and we want to find two members in the array (must be unique items, e.g, cannot be A[i] + A[i]) that has the sum of s.

With Brute-Force approach, we actually scan the array from i=0 to n-1 and check if the sum with its next item equals s.

For example, a Python code like below:


A = [-1, 3, 5, 6, -2, 10, 7, 9, 8, 4]

s = int(input("Enter the wanted sum: "))

# brute-force

for k in range(len(A)-1):
    for l in range(k+1,len(A)):
        if A[k] + A[l] == s:
            print("Found it: A[%d]+A[%d] = %d" % (k,l,s))
            print("\t%d+%d = %d" % (A[k],A[l],s))

The problem with this approach is obviously not optimal (the complexity is O(n2)).

A better method is if we don't need to walk through the array second time (the second loop).  We still need to walk through each item in the list, though.

def ArrayToDict(A):
    h = {}
    for i in enumerate(A):
        key = i[1]
        val = i[0]
        h.setdefault(key, []).append(val)
    return h

def IsValExist(H,k):
H = ArrayToDict(A)
for enum in enumerate(A):

    ret = True
        ret = False
    return ret

    i = enum[0]
    v = m - A[i]
    if IsValExist(H,v):
        for iv in H[v]:
            if iv != i:
                print("GOT IT: A[%d](%d) + A[%d] (%d) = %d" % (i, A[i], iv, A[iv], m))

With this approach, the complexity is only O(n) (assuming only very few key duplicates, if any, in the hash/dictionary).

No comments:

Post a Comment