Find Positive Integer Solution for a Given Equation — LeetCode 1237 Python Solution

The problem

Given a callable function f(x, y) with a hidden formula and a value z, reverse engineer the formula and return all positive integer pairs x and y where f(x,y) == z. You may return the pairs in any order.

Example

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

Python solution

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):

"""


class Solution:
    def findSolution(self, customfunction: "CustomFunction", z: int) -> List[List[int]]:
        ans = []
        for x in range(1, z + 1):
            y = 1 + bisect_left(
                range(1, z + 1), z, key=lambda y: customfunction.f(x, y)
            )
            if customfunction.f(x, y) == z:
                ans.append([x, y])
        return ans

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1237. Find Positive Integer Solution for a Given Equation is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems