Problem Description

You are given a function f(x, y) where x and y are positive integers. The function is strictly increasing with respect to both variables: that is, f(x, y) < f(x + 1, y) and f(x, y) < f(x, y + 1) for all positive integers x and y.

Given a target value z, your task is to find all positive integer pairs (x, y) such that f(x, y) == z. The function f is provided as an interface or black box (you can only call it, not examine its code).

Constraints:

• You must find all valid pairs (x, y) such that both x and y are positive integers.
• You cannot reuse elements – each pair must be unique.
• The search space is limited: typically, 1 ≤ x, y ≤ 1000.
• There may be zero, one, or multiple solutions.

Thought Process

At first glance, the problem could be solved using a brute-force approach: try every possible pair (x, y) in the allowed range and check if f(x, y) == z. However, since f is strictly increasing with respect to both variables, we can use this property to optimize our search.

The strictly increasing nature means:

• If f(x, y) < z, you need to increase x or y to get closer to z.
• If f(x, y) > z, you need to decrease x or y to get closer to z.

Solution Approach

Here’s how to efficiently find all solutions:

1. Initialize: Start with x = 1 and y = max_y (e.g., 1000). This positions us at the top-left or bottom-left of the search grid.
2. Iterate: While x is within range and y is within range:
   • Call f(x, y).
   • If f(x, y) == z, record (x, y) as a solution, then increment x (since increasing y will only make f(x, y) larger).
   • If f(x, y) < z, increment x to increase the value.
   • If f(x, y) > z, decrement y to decrease the value.
3. Termination: Stop when x or y go out of bounds.

This approach ensures that each pair is checked at most once, and the search space is pruned efficiently using the strictly increasing property.

Example Walkthrough

Suppose f(x, y) = x * y and z = 5. We want all positive integer pairs (x, y) such that x * y = 5.

1. Start with x = 1, y = 1000 (or the max allowed value).
2. Check f(1, 1000) = 1000 (too big), so decrement y to 999, 998, ..., until y = 5.
3. At f(1, 5) = 5, record (1, 5).
4. Increment x to 2, check f(2, 5) = 10 (too big), so decrement y to 4, 3, etc. No solution.
5. Continue until x = 5, y = 1 where f(5, 1) = 5. Record (5, 1).
6. All other pairs either overshoot or undershoot z.

The pairs found are (1, 5) and (5, 1).

Time and Space Complexity

Brute-force approach: Tries all possible (x, y) pairs in the range, leading to O(N²) time complexity (where N is the upper bound, e.g., 1000).

Optimized approach: Since each step either increments x or decrements y, the maximum number of steps is O(N) + O(N) = O(N). Thus, the optimized solution is linear in the size of the range.

Space complexity: Only the output list of solutions is stored, so space is O(K), where K is the number of valid pairs.

Summary

By leveraging the strictly increasing property of the function f(x, y), we avoid brute-force search and instead use a two-pointer-like approach. This enables us to efficiently scan the grid of possible solutions, ensuring each pair is considered only once. The key insight is to adjust x and y based on whether the current value is less than or greater than the target, similar to searching in a sorted matrix. This makes the solution both elegant and highly efficient.

Code Implementation

# Suppose f is provided as follows:
# For testing, let's use f(x, y) = x * y
def f(x, y):
    return x * y

def findSolution(customfunction, z):
    res = []
    x, y = 1, 1000
    while x <= 1000 and y >= 1:
        val = customfunction(x, y)
        if val == z:
            res.append([x, y])
            x += 1
        elif val < z:
            x += 1
        else:
            y -= 1
    return res
      

/*
Suppose CustomFunction is a class with int f(int x, int y);
For testing, f(x, y) = x * y
*/
class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        int x = 1, y = 1000;
        while (x <= 1000 && y >= 1) {
            int val = customfunction.f(x, y);
            if (val == z) {
                res.push_back({x, y});
                x++;
            } else if (val < z) {
                x++;
            } else {
                y--;
            }
        }
        return res;
    }
};
      

/*
Suppose CustomFunction has int f(int x, int y);
For testing, f(x, y) = x * y
*/
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<>();
        int x = 1, y = 1000;
        while (x <= 1000 && y >= 1) {
            int val = customfunction.f(x, y);
            if (val == z) {
                res.add(Arrays.asList(x, y));
                x++;
            } else if (val < z) {
                x++;
            } else {
                y--;
            }
        }
        return res;
    }
}
      

/*
Suppose customfunction.f(x, y) is provided.
For testing, f(x, y) = x * y
*/
var findSolution = function(customfunction, z) {
    const res = [];
    let x = 1, y = 1000;
    while (x <= 1000 && y >= 1) {
        const val = customfunction.f(x, y);
        if (val === z) {
            res.push([x, y]);
            x++;
        } else if (val < z) {
            x++;
        } else {
            y--;
        }
    }
    return res;
};