Give an array, find four unique ints that satisfy the following equation

user_13933287 0
Viewed 181

So I currently have a question that I'm attempting to solve:

  • Given an array of L distinct integers that are all > 0, find if there are four integers that are unique that solve the following equation of a^2 + b - c^2 - d = 0

I have to solve this problem with time complexity of O(n^2).

This is my current failing attempt at solving the problem:

I first rearrange the equation to make a^2 + b = c^2 + d, then I initialise a hash map. I use a nested for loop to get pairs of elements. I save the sum of the first element squared + the second element. I then check if it is in the hash map. If it is, I then return true as I found another distinct pair, else if not, I add it in the hashmap.

def solution(arr, n):
  
    Hash = {} # Introduce a hash map
      
    # Create a double for loop
    for i in range(n - 1):
        for j in range(i + 1, n):
            eqt = arr[i]* arr[i] + arr[j] # Take the sum
 
            if eqt in Hash.keys():
                # Return true as another pair has been found
                print('Found')
                return True
            else:
                # Sum isnt in hash so store it
                Hash[eqt] = (arr[i], arr[j])
    return False

This solution seems to work for arrays that are ordered, but when they aren't, it fails i.e: it works for [1,2,3,4,5,6,7] => producing (1, 6) and (2, 3) but doesn't work for [7,6,5,4,3,2,1].

Any guidance or help is greatly appreciated, thanks.

algorithm python
1 Answers

The issue is at the range of the inner loop variable, j. It only looks after the i; but it should also look all the values (except ith) in the arr, not only after i.

So, fix is

def solution(arr, n):

    Hash = {} # Introduce a hash map

    # Create a double for loop
    for i in range(n):
        for j in range(n):                   # main change is here!
            if i == j:                       # and here (excluding same element)
                continue

            eqt = arr[i]* arr[i] + arr[j] # Take the sum

            if eqt in Hash:
                # Return False as another pair has been found
                print("Found")
                return False
            else:
                # Sum isnt in hash so store it
                Hash[eqt] = (arr[i], arr[j])
    return True

Some other changes:

  • It should return False I think when it finds a pair in the hash (according to the problem description, I understood this way)
  • for i in range(n) instead of n-1 to let it look at the last value too; complexity is the same overall
  • eqt in Hash instead of over keys; same thing but more Pythonic

Testing:

>>> solution([1,2,3,4,5,6,7], 7)
False
>>> solution([7,6,5,4,3,2,1], 7)
False

To assure distinctness of the pairs, we modify the if as (as @JoranBeasley mentions):

if eqt in Hash and not any(val in Hash[eqt] for val in (arr[i], arr[j])):
    ...

to check not any of the values in the candidate at hand i.e., arr[i], arr[j] is in the already-found pair i.e., Hash[eqt].

user_93321870
Related