Scale Engineer

Find Positive Integer Solution for a Given Equation

Med
#1155Time: 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).
Patterns
MathTwo Pointers
Algorithms
Binary Search

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

/* * // 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;    }}

Complexity

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

Trade-offs

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.

Solutions

/* * // 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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem