CODEWITHSUNDEEP
python-2.7performancefor-loopexecution-time
spontaneous_coder
spontaneous_coder

Reputation: 117

Find pair from 2 list whose sum is equal to given value

We have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

For example: For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be

sumOfTwo(a, b, v) = True

My code so far:

def sumOfTwo(a, b, v):
    for x in a:
        for y  in b:
            if x+y == v:
                return True
    return False

I want to reduce the execution time, as its taking long to execute long lists.

Upvotes: 1

Views: 1454

Answers (1)

myrtlecat
myrtlecat

Reputation: 2276

It should be much faster if you first convert b to a set:

def sumOfTwo(a, b, v):
    b = set(b)
    return any(v - x in b for x in a)

The complexity should be O(M + N) in stead of O(MN) for the brute force solution.

Upvotes: 1

Related Questions