Find Positive Integer Solution for a Given Equation - Video Solutions
1237. Find Positive Integer Solution for a Given Equation
Find Positive Integer Solution for a Given Equation - Video Solution
Watch 10 video solutions for Find Positive Integer Solution for a Given Equation, a medium level problem involving Math, Two Pointers, Binary Search. This walkthrough by Math Geeks has 1,116 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
9hidden implementations ofCustomFunction, along with a way to generate an answer key of all valid pairs for a specificz. - The judge will receive two inputs: a
function_id(to determine which implementation to test your code with), and the targetz. - The judge will call your
findSolutionand compare your results with the answer key. - If your results match the answer key, your solution will be
Accepted.
Example 1:
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 <= 91 <= z <= 100- It is guaranteed that the solutions of
f(x, y) == zwill be in the range1 <= x, y <= 1000. - It is also guaranteed that
f(x, y)will fit in 32 bit signed integer if1 <= x, y <= 1000.
Approach Overview
Problem Overview: You are given a hidden monotonic function f(x, y) and an integer z. The goal is to find all positive integer pairs (x, y) such that f(x, y) = z. The function increases as either x or y increases, which guarantees ordered behavior that can be exploited for faster search.
Approach 1: Brute-force Search Method (O(n^2) time, O(1) space)
The most direct solution checks every possible pair (x, y) within the valid range (typically 1 ≤ x, y ≤ 1000). For each pair, call the provided API f(x, y) and compare the result with z. If the result matches, store the pair. This approach works because the search space is bounded, but it performs up to one million function calls. While acceptable for small limits, it ignores the key property of the function: monotonic growth. Use this approach mainly to verify correctness or when constraints are extremely small.
Approach 2: Two-pointer Approach (O(n) time, O(1) space)
The function increases with both variables. That means if f(x, y) is too large, increasing y further will only increase the value. This monotonic property allows a classic two pointers strategy. Start with x = 1 and y = 1000. Compute f(x, y). If the value equals z, record the pair and move both pointers (x++, y--) to continue searching. If the value is smaller than z, increase x to raise the function value. If it is larger than z, decrease y. Each step eliminates an entire row or column of the search grid, reducing the complexity to linear time. This pattern frequently appears in problems combining math properties with ordered search.
Another valid variation uses binary search: for each fixed x, binary search the value of y that satisfies f(x, y) = z. That runs in O(n log n), but the two-pointer scan is simpler and faster.
Recommended for interviews: The two-pointer approach is what interviewers typically expect. It demonstrates that you recognized the monotonic behavior of the function and converted a quadratic search into a linear scan. Showing the brute-force method first proves baseline reasoning, but switching to the optimized two-pointer solution highlights algorithmic thinking and pattern recognition.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-force Search | O(n^2) | O(1) | Useful for small bounds or validating logic when first approaching the problem. |
| Binary Search per x | O(n log n) | O(1) | Works when the function is strictly increasing in y for each fixed x. |
| Two-pointer Scan | O(n) | O(1) | Best choice when both variables produce monotonic increases, enabling elimination of rows or columns. |