#1237

Find Positive Integer Solution for a Given Equation

specialist · 635 · lc medium +30 · verified · 69.9% accepted · 546 likes · top 78%

Description

You are given access to a callable function f(x, y) with a hidden formula and a target value z. Find all pairs of positive integers x and y such that f(x, y) == z.

The function is monotonically increasing in both arguments:

- f(x, y) < f(x + 1, y)

- f(x, y) < f(x, y + 1)

Return all valid pairs [x, y] in any order.

Example 1:

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);

};

Example 2:

Input: function_id = 1, z = 5

Output: [[1,4],[2,3],[3,2],[4,1]]

Explanation: The hidden formula for function_id = 1 is f(x, y) = x + y.

The following positive integer values of x and y make f(x, y) equal to 5:

x=1, y=4 -> f(1, 4) = 1 + 4 = 5.

x=2, y=3 -> f(2, 3) = 2 + 3 = 5.

x=3, y=2 -> f(3, 2) = 3 + 2 = 5.

x=4, y=1 -> f(4, 1) = 4 + 1 = 5.

Example 3:

Input: function_id = 2, z = 5

Output: [[1,5],[5,1]]

Explanation: The hidden formula for function_id = 2 is f(x, y) = x * y.

The following positive integer values of x and y make f(x, y) equal to 5:

x=1, y=5 -> f(1, 5) = 1 * 5 = 5.

x=5, y=1 -> f(5, 1) = 5 * 1 = 5.

Code

"""
   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]]:

"""
   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]]: