Finding two variables from different arrays to get a specific sum in specific complexity-CodePudding

I'm a computer science student and it my first year! So, I see this have to be very easy but some how I just can't catch it in my head.

So - exercise it self:

Def gets two arrays with real numbers (ints) and some S (int). Need to find X (some int from array 1) Y (int from array 2) = S. BUT - complexity has to be O(n m) where n & m are lengths of arrays.

def finding_sum(arr1, arr2, s):
  for i in arr1:
    if (s-i in arr2):
      return i, s-i

I thought about that - but IN module is just like going through the full array and this is O(n*m).

CodePudding user response：

You can create an auxiliary data structure:

def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    for n in arr2:
        if n in lookup:
            return s-n, n

The set lookup takes linear time to create and provides a O(1) contains check. You can shorten this using next:

def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    return next((s-n, n) for n in arr2 if n in lookup)

CodePudding user response：

Convert the second list to a set. The conversion is O(m),and set lookup is O(1).

def finding_sum(arr1, arr2, s):
    set2 = set(arr2)
    for i in arr1:
        if s-i in set2:
            return i, s-i