# Find Positive Integer Solution for a Given Equation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation)
Canonical: https://scaleengineer.com/dsa/problems/find-positive-integer-solution-for-a-given-equation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
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`.

# Approaches
## Brute Force with Pruning
The most straightforward approach is to test all possible pairs of `(x, y)` in the given range `[1, 1000]`. We can use nested loops to iterate through each `x` from 1 to 1000 and each `y` from 1 to 1000. However, a naive brute-force search would be very inefficient. We can significantly optimize it by using the monotonically increasing property of the function `f(x, y)`. If at any point `f(x, y)` becomes greater than `z`, we know that for any `y' > y`, `f(x, y')` will also be greater than `z`. This allows us to 'prune' the search space by breaking the inner loop early.
**Time:** O(X * Y) in the worst case, where X and Y are the maximum values of x and y (1000). Although pruning helps significantly in practice (especially with a small `z`), the theoretical worst-case complexity remains quadratic. · **Space:** O(N), where N is the number of solutions found. This space is used to store the result list. The auxiliary space complexity is O(1).
**Pros:** Relatively simple to understand and implement.; It's a direct translation of the problem statement into code.; Guaranteed to find all solutions within the given range.
**Cons:** This approach is inefficient as it may perform a large number of function calls, especially if `z` is large.; The worst-case time complexity is quadratic, which is significantly slower than other available methods.
### Explanation
This method involves a systematic check of `(x, y)` pairs using nested loops. The outer loop iterates through `x` and the inner loop iterates through `y`. The key optimization comes from the monotonic property of `f(x, y)`. For a fixed `x`, as we increase `y`, the value of `f(x, y)` increases. If `f(x, y)` exceeds the target `z`, there's no need to check larger values of `y` for the current `x`, so we can break the inner loop. A similar optimization can be applied to the outer loop.

```java
/*
 * // 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 x and y.
 *     // i.e. f(x, y) < f(x + 1, y) and f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
import java.util.Arrays;

class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
        for (int x = 1; x <= 1000; x++) {
            if (customfunction.f(x, 1) > z) {
                break; // Optimization for the outer loop
            }
            for (int y = 1; y <= 1000; y++) {
                int val = customfunction.f(x, y);
                if (val == z) {
                    result.add(Arrays.asList(x, y));
                    break; // Found solution for this x, move to next x
                } else if (val > z) {
                    break; // Prune the search for current x
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the solution pairs.
- Iterate with a variable `x` from 1 to 1000.
- For each `x`, check if `customfunction.f(x, 1) > z`. If it is, we can stop searching, as all subsequent values of `f(x', y)` for `x' >= x` will also be greater than `z`.
- Inside the loop for `x`, start another loop for `y` from 1 to 1000.
- Calculate `val = customfunction.f(x, y)`.
- If `val == z`, add the pair `[x, y]` to the `result` list. Since `f` is strictly increasing with `y`, we can break the inner loop and continue with the next `x`.
- If `val > z`, we can break the inner loop for `y`. Because the function is monotonically increasing, `customfunction.f(x, y+1)` will also be greater than `z`.
- If `val < z`, continue the inner loop to check the next `y`.
- After the loops complete, return the `result` list.

## Iteration with Binary Search
A more optimized approach leverages the monotonic property of the function more effectively. For any fixed value of `x`, the function `f(x, y)` is strictly increasing with respect to `y`. This means we can use binary search to find the corresponding `y` for a given `x` such that `f(x, y) = z`. We can iterate through all possible values of `x` and, for each `x`, perform a binary search on `y`.
**Time:** O(X * log Y), where X and Y are the maximum values for x and y. The outer loop runs X times, and each binary search takes O(log Y) time. · **Space:** O(N), where N is the number of solutions. This space is for the output list. The auxiliary space is O(1).
**Pros:** Significantly more efficient than the brute-force approach.; Effectively utilizes the monotonic property of the function.
**Cons:** While more efficient than brute force, it is not the most optimal solution.; It still involves an outer loop that iterates up to 1000 times.
### Explanation
The algorithm iterates through each possible value of `x` from 1 to 1000. For each `x`, it treats `f(x, y)` as a function of `y` and tries to solve `f(x, y) = z`. Since `f` is increasing in `y`, we can efficiently find if a solution `y` exists using binary search over the range of possible `y` values, which is `[1, 1000]`. If the binary search finds a `y` that satisfies the equation, the pair `(x, y)` is added to our list of solutions.

```java
/*
 * // 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 x and y.
 *     // i.e. f(x, y) < f(x + 1, y) and f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
import java.util.Arrays;

class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
        for (int x = 1; x <= 1000; x++) {
            int low = 1, high = 1000;
            while (low <= high) {
                int y = low + (high - low) / 2;
                int val = customfunction.f(x, y);
                if (val == z) {
                    result.add(Arrays.asList(x, y));
                    break; // Found the unique y for this x
                } else if (val < z) {
                    low = y + 1;
                } else {
                    high = y - 1;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Iterate through `x` from 1 to 1000.
- For each `x`, the function `g(y) = f(x, y)` is a monotonically increasing function of `y`. We can use binary search to find a `y` in the range `[1, 1000]` such that `g(y) == z`.
- Set up binary search pointers `low = 1` and `high = 1000`.
- While `low <= high`:
    - Calculate `mid = low + (high - low) / 2`.
    - Get the value `val = customfunction.f(x, mid)`.
    - If `val == z`, we've found a solution `(x, mid)`. Add it to the result and break the binary search for the current `x` (since `y` must be unique for a given `x`).
    - If `val < z`, we need a larger value, so we search in the upper half by setting `low = mid + 1`.
    - If `val > z`, we need a smaller value, so we search in the lower half by setting `high = mid - 1`.
- Return the `result` list.

## Two Pointers / Search Space Reduction
The most efficient solution treats the problem as a search in a 2D space. If we imagine a grid where `x` represents columns and `y` represents rows, the value at `(x, y)` is `f(x, y)`. Due to the monotonic property, this grid is sorted in both ascending order along rows (increasing `x`) and ascending order along columns (increasing `y`). This structure is similar to a row-wise and column-wise sorted matrix. We can search this space efficiently using a two-pointer approach, starting from a corner and eliminating a row or a column in each step.
**Time:** O(X + Y), where X and Y are the maximum values for x and y. In each step, we either increment x or decrement y. Since x moves from 1 to X and y moves from Y to 1, the total number of steps is at most X + Y. · **Space:** O(N), where N is the number of solutions. This space is for the output list. The auxiliary space complexity is O(1).
**Pros:** This is the most efficient approach with a linear time complexity.; It makes the best use of the monotonic property of the function.; It performs the minimum number of calls to the custom function.
**Cons:** The logic might be slightly less intuitive to come up with compared to brute-force or binary search approaches.
### Explanation
This approach uses a clever search space reduction technique. We start at the 'bottom-left' corner of the search space, with `x = 1` and `y = 1000`. We then evaluate `f(x, y)`.
- If `f(x, y) > z`, it means the current value is too high. To get a smaller value, we must decrease one of the inputs. Since `x` is already at its minimum, we can only decrease `y`. This effectively eliminates the entire row `y` from our search space.
- If `f(x, y) < z`, the value is too low. To get a larger value, we must increase one of the inputs. We increase `x`, which effectively eliminates the column `x` from our search space.
- If `f(x, y) == z`, we've found a solution. We add it to our results and move both pointers (`x++`, `y--`) to continue searching for other possible solutions on the diagonal path.
This process continues until the pointers cross (`x > 1000` or `y < 1`), having covered the entire search space in linear time.

```java
/*
 * // 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 x and y.
 *     // i.e. f(x, y) < f(x + 1, y) and f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
import java.util.Arrays;

class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
        int x = 1;
        int y = 1000;
        while (x <= 1000 && y >= 1) {
            int val = customfunction.f(x, y);
            if (val == z) {
                result.add(Arrays.asList(x, y));
                x++;
                y--;
            } else if (val < z) {
                x++;
            } else { // val > z
                y--;
            }
        }
        return result;
    }
}
```
### Algorithm
- Visualize the `(x, y)` pairs and their function values `f(x, y)` as a 2D matrix that is sorted row-wise and column-wise.
- Initialize two pointers: `x = 1` (starting from the first column) and `y = 1000` (starting from the last row).
- Initialize an empty list `result`.
- Loop as long as `x <= 1000` and `y >= 1`:
    - Calculate `val = customfunction.f(x, y)`.
    - If `val == z`, a solution is found. Add `[x, y]` to `result`. To find other potential solutions, we must move to a different state. We increment `x` and decrement `y` to continue the search.
    - If `val < z`, we need a larger value. Since `f(x, y)` increases with `x`, we increment `x` to `x+1`.
    - If `val > z`, we need a smaller value. Since `f(x, y)` increases with `y`, we decrement `y` to `y-1`.
- Return the `result` list.

# Solutions
### Java

```java
/* * // 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) * public int f(int x, int y); * }; */ class Solution { public List < List < Integer >> findSolution ( CustomFunction customfunction , int z ) { List < List < Integer >> ans = new ArrayList <>(); for ( int x = 1 ; x <= 1000 ; ++ x ) { int l = 1 , r = 1000 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( customfunction . f ( x , mid ) >= z ) { r = mid ; } else { l = mid + 1 ; } } if ( customfunction . f ( x , l ) == z ) { ans . add ( Arrays . asList ( x , l )); } } return ans ; } }
```

### CPP

```cpp
/* * // This is the custom function interface. * // You should not implement it, or speculate about its implementation * class CustomFunction { * public: * // 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) * int f(int x, int y); * }; */ class Solution { public: vector < vector < int >> findSolution ( CustomFunction & customfunction , int z ) { vector < vector < int >> ans ; for ( int x = 1 ; x <= 1000 ; ++ x ) { int l = 1 , r = 1000 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( customfunction . f ( x , mid ) >= z ) { r = mid ; } else { l = mid + 1 ; } } if ( customfunction . f ( x , l ) == z ) { ans . push_back ({ x , l }); } } return ans ; } };
```

### Python

```python
""" 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
```