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,105 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
9 hidden implementations of CustomFunction, along with a way to generate an answer key of all valid pairs for a specific z.function_id (to determine which implementation to test your code with), and the target z.findSolution and compare your results with the answer key.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 <= 100f(x, y) == z will be in the range 1 <= x, y <= 1000.f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000.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.
| 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. |