[LeetCode]#1237. Find Positive Integer Solution for a Given Equation

Environment: Python 3.7

Key technique: if

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

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

The function interface is defined like this:

interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};

For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you'll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Analysis:

  1. We don’t know all function.
  2. Use linear search. x is 1 to 1000 and y is 1000 to 1.
  3. if f(x,y) >z , y=y-1
  4. if f(x,y) <z, x=x+1
  5. if f(x,y)=z, record [x,y].
  6. Return all f(x,y) answer.

Solution:

class Solution:
def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
ans=[]
x=1
y=1000
while x<=1000 and y>=1:
fxy=customfunction.f(x,y)
if fxy>z:
y-=1
elif fxy<z:
x+=1
else:
ans.append([x,y])
x+=1
return ans

Submissions:

Reference:

https://blog.csdn.net/CSerwangjun/article/details/102774683

Interesting in any computer science.