1237. Find Positive Integer Solution for a Given Equation LeetCode Solution
In this guide, you will get 1237. Find Positive Integer Solution for a Given Equation LeetCode Solution with the best time and space complexity. The solution to Find Positive Integer Solution for a Given Equation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Positive Integer Solution for a Given Equation
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.
While the exact formula is hidden, the function is monotonically 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 some positive integer f(x, y) for two positive integers x and y based on a formula.
int f(int x, int y);
};
We will judge your solution as follows:
The judge has a list of 9 hidden implementations of CustomFunction, along with a way to generate an answer key of all valid pairs for a specific z.
The judge will receive two inputs: a function_id (to determine which implementation to test your code with), and the target z.
The judge will call your findSolution and compare your results with the answer key.
If your results match the answer key, your solution will be Accepted.
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 2:
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.
Constraints:
1 <= function_id <= 9
1 <= z <= 100
It is guaranteed that the solutions of f(x, y) == z will be in the range 1 <= x, y <= 1000.
It is also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000.
Complexity Analysis
Time Complexity:
Space Complexity:
1237. Find Positive Integer Solution for a Given Equation LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int>> ans;
int x = 1;
int y = 1000;
while (x <= 1000 && y >= 1) {
int f = customfunction.f(x, y);
if (f < z)
++x;
else if (f > z)
--y;
else
ans.push_back({x++, y--});
}
return ans;
}
}; /* code provided by PROGIEZ */
1237. Find Positive Integer Solution for a Given Equation LeetCode Solution in Java
class Solution {
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> ans = new LinkedList<>();
int x = 1;
int y = 1000;
while (x <= 1000 && y >= 1) {
int f = customfunction.f(x, y);
if (f < z)
++x;
else if (f > z)
--y;
else
ans.add(Arrays.asList(x++, y--));
}
return ans;
}
} // code provided by PROGIEZ
1237. Find Positive Integer Solution for a Given Equation LeetCode Solution in Python
class Solution:
def findSolution(self, customfunction: 'CustomFunction', z: int) -> list[list[int]]:
ans = []
x = 1
y = 1000
while x <= 1000 and y >= 1:
f = customfunction.f(x, y)
if f < z:
x += 1
elif f > z:
y -= 1
else:
ans.append([x, y])
x += 1
y -= 1
return ans # code by PROGIEZ
