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.
The simplest approach is to iterate through all possible values of x and y within the given constraints. For every x (from 1 to 1000), calculate the corresponding y such that f(x, y) == z. Since the function f(x, y) is monotonically increasing, this method will eventually find all pairs that satisfy the condition. This is a brute-force method and is not the most efficient due to its O(n^2) time complexity.
This C code iterates over all possible pairs of integers x and y starting from 1 up to 1000. It calls a function f(x, y) to check if it matches the target z. When a match is found, it prints the pair. The loop for y breaks early if f(x, y) exceeds z, utilizing the monotonically increasing property.
Time Complexity: O(n^2), where n is the maximum bound (1000).
Space Complexity: O(1), as we are not using extra space proportional to input size.
Given that the function is monotonically increasing, an efficient approach involves using two pointers. Start one pointer at the beginning of a range (say x from 1 to 1000) and the other at the end (y starting from 1000). Adjust the pointers based on the result of f(x, y) compared to z. If f(x, y) > z, decrement y, else increment x. Keep adjusting until all solutions are found.
This C code implements the two-pointer approach. The code starts with pointers x at 1 and y at 1000. Adjustments are made based on the comparison of f(x, y) with z. When the sum equals z, both pointers are adjusted to continue searching for other combinations. This reduces unnecessary computations.
Time Complexity: O(n), where n is the range (1000).
Space Complexity: O(1), as results are generated and stored dynamically.
According to the problem, we know that the function f(x, y) is a monotonically increasing function. Therefore, we can enumerate x, and then binary search y in [1,...z] to make f(x, y) = z. If found, add (x, y) to the answer.
The time complexity is O(n log n), where n is the value of z, and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
We can define two pointers x and y, initially x = 1, y = z.
f(x, y) = z, we add (x, y) to the answer, then x \leftarrow x + 1, y \leftarrow y - 1;f(x, y) \lt z, at this time for any y' \lt y, we have f(x, y') \lt f(x, y) \lt z, so we cannot decrease y, we can only increase x, so x \leftarrow x + 1;f(x, y) \gt z, at this time for any x' \gt x, we have f(x', y) \gt f(x, y) \gt z, so we cannot increase x, we can only decrease y, so y \leftarrow y - 1.After the loop ends, return the answer.
The time complexity is O(n), where n is the value of z, and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute-force Search Method | Time Complexity: O(n^2), where n is the maximum bound (1000). |
| Two-pointer Approach | Time Complexity: O(n), where n is the range (1000). |
| Enumeration + Binary Search | — |
| Two Pointers | — |
| 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. |
1237. Find Positive Integer Solution for a Given Equation • Math Geeks • 1,105 views views
Watch 9 more video solutions →Practice Find Positive Integer Solution for a Given Equation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor