#1237

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Positive Integer Solution for a Given Equation

Determine all positive integer pairs that satisfy a hidden monotonic function for a given target using binary search over possible values.

math two pointers binary search interactive

Problem Statement

You are given a callable function f(x, y) with an unknown formula and a positive integer target z. The function is guaranteed to be monotonically increasing with respect to both x and y. Your task is to return all pairs of positive integers (x, y) where f(x, y) equals z. You may return the pairs in any order.

The interface provides the function f through a hidden implementation and limits x and y to the range 1 to 1000. You should design an approach that efficiently checks potential pairs without iterating all 1,000,000 possibilities. Consider using binary search over the answer space or a two-pointer strategy to leverage the monotonic property.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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); };

Example 2

Input: function_id = 1, z = 5

Output: [[1,4],[2,3],[3,2],[4,1]]

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 3

Input: function_id = 2, z = 5

Output: [[1,5],[5,1]]

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.

Solution Approach

Loop with Two Pointers

Start with x = 1 and y = 1000, then iteratively check f(x, y). If f(x, y) is greater than z, decrement y; if less, increment x. This takes advantage of the monotonic property and avoids a full O(n^2) search.

Binary Search per x

For each x from 1 to 1000, perform a binary search on y in the range 1 to 1000 to find y such that f(x, y) == z. This reduces unnecessary checks and ensures logarithmic exploration in y.

Combine Both Strategies

Use two pointers to move across the potential solution space while applying binary search where the function grows steeply. This hybrid approach balances iteration and search, minimizing total function calls.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n log n) using binary search per x to O(n) with a two-pointer approach, where n = 1000. Space complexity is O(1) aside from storing the result pairs.

What Interviewers Usually Probe

Are you considering how the monotonic property can eliminate unnecessary checks?
Can you optimize function calls instead of brute forcing all pairs?
How will you ensure that all valid pairs are returned without duplicates?

Common Pitfalls or Variants

Common pitfalls

Brute forcing all 1,000,000 x-y pairs without leveraging monotonicity.
Assuming the function can be directly inverted without checking integer constraints.
Failing to handle edge cases where x or y equals 1 or 1000.

Follow-up variants

Find pairs for a non-monotonic hidden function requiring full enumeration.
Return solutions where f(x, y) is within a tolerance range instead of exact z.
Optimize for very large ranges, e.g., 1 <= x, y <= 10^6, using modified search strategies.

FAQ

What is the main strategy to solve 'Find Positive Integer Solution for a Given Equation'?

The key is to exploit the monotonic property with two pointers or binary search, checking pairs efficiently instead of brute force.

Why can’t we iterate over all x and y values directly?

Iterating all 1,000,000 combinations is inefficient; leveraging monotonicity drastically reduces the number of required function calls.

How does binary search help in this problem?

Binary search narrows down the possible y for each x quickly by exploiting the increasing nature of f(x, y).

Are duplicates possible in the output pairs?

No, each valid (x, y) pair is unique due to the strictly increasing property of f(x, y).

Can this approach handle maximum constraints efficiently?

Yes, combining two-pointer traversal with binary search ensures it works efficiently for x and y up to 1000.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):

"""


class Solution:
    def findSolution(self, customfunction: "CustomFunction", z: int) -> List[List[int]]:
        ans = []
        for x in range(1, z + 1):
            y = 1 + bisect_left(
                range(1, z + 1), z, key=lambda y: customfunction.f(x, y)
            )
            if customfunction.f(x, y) == z:
                ans.append([x, y])
        return ans

Solution 2: Two Pointers

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):

"""


class Solution:
    def findSolution(self, customfunction: "CustomFunction", z: int) -> List[List[int]]:
        ans = []
        for x in range(1, z + 1):
            y = 1 + bisect_left(
                range(1, z + 1), z, key=lambda y: customfunction.f(x, y)
            )
            if customfunction.f(x, y) == z:
                ans.append([x, y])
        return ans

Continue Practicing

#633 sum of square numbers #1201 ugly number iii #1346 check if n and its double exist