Skip to main content
Talentd

Find Positive Integer Solution for a Given Equation - Solution & Explanation

MediumMathTwo PointersBinary SearchInteractive26 min readAsked at: Google, Tiktok
Practice this problem

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 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.

 

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 <= 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.

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.

Approach 1: Brute-force Search Method

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Two-pointer Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the range (1000).
Space Complexity: O(1), as results are generated and stored dynamically.

Try this approach in the editor →

Approach 3: Enumeration + Binary Search

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Two Pointers

We can define two pointers x and y, initially x = 1, y = z.

  • If f(x, y) = z, we add (x, y) to the answer, then x \leftarrow x + 1, y \leftarrow y - 1;
  • If 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;
  • If 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute-force Search Method

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.

Two-pointer Approach

Time Complexity: O(n), where n is the range (1000).
Space Complexity: O(1), as results are generated and stored dynamically.

Enumeration + Binary Search—
Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-force SearchO(n^2)O(1)Useful for small bounds or validating logic when first approaching the problem.
Binary Search per xO(n log n)O(1)Works when the function is strictly increasing in y for each fixed x.
Two-pointer ScanO(n)O(1)Best choice when both variables produce monotonic increases, enabling elimination of rows or columns.

Video Solution

1237. Find Positive Integer Solution for a Given Equation • Math Geeks • 1,116 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Positive Integer Solution for a Given Equation easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing that the custom function is strictly increasing, which allows replacing a naive O(n^2) search with a linear two-pointer scan.
Find Positive Integer Solution for a Given Equation Python/Java solution
In Python or Java, implement a loop with two pointers: x starting at 1 and y starting at 1000. Repeatedly call f(x, y) and adjust pointers depending on whether the result is less than, greater than, or equal to z. Store valid pairs in a result list.
How to solve Find Positive Integer Solution for a Given Equation in O(n)?
Use a two-pointer scan across the search grid. Start with x=1 and y=1000. If f(x,y) equals z, record the pair and move both pointers. If the value is smaller than z, increase x; if larger, decrease y. Each move removes a full row or column from consideration, producing O(n) complexity.
What is the best approach for Find Positive Integer Solution for a Given Equation?
The two-pointer approach is the optimal solution. Because the custom function f(x, y) increases as either x or y increases, you can start from (x=1, y=1000) and move pointers based on whether the computed value is smaller or larger than z. This reduces the search from O(n^2) to O(n).
Is Find Positive Integer Solution for a Given Equation asked at Google/Amazon/Meta?
Problems involving monotonic functions and two-pointer search patterns commonly appear in interviews at companies like Google, Amazon, and Meta. The question tests reasoning about ordered search spaces and reducing brute-force complexity.
What data structure is used in Find Positive Integer Solution for a Given Equation?
No specialized data structure is required. The solution mainly relies on pointer variables and repeated calls to the provided API function. The key concept is exploiting monotonic behavior rather than storing intermediate data.
What is the time complexity of Find Positive Integer Solution for a Given Equation?
The optimal two-pointer solution runs in O(n) time with O(1) extra space, where n is the maximum possible value of x or y (commonly 1000). A brute-force solution that checks every pair requires O(n^2) time.

Ready to solve this problem?

Practice Find Positive Integer Solution for a Given Equation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer