Find Positive Integer Solution for a Given Equation
MedPrompt
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
9hidden implementations ofCustomFunction, along with a way to generate an answer key of all valid pairs for a specificz. - The judge will receive two inputs: a
function_id(to determine which implementation to test your code with), and the targetz. - The judge will call your
findSolutionand 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 <= 91 <= z <= 100- It is guaranteed that the solutions of
f(x, y) == zwill be in the range1 <= x, y <= 1000. - It is also guaranteed that
f(x, y)will fit in 32 bit signed integer if1 <= 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
resultto store the solution pairs. - Iterate with a variable
xfrom 1 to 1000. - For each
x, check ifcustomfunction.f(x, 1) > z. If it is, we can stop searching, as all subsequent values off(x', y)forx' >= xwill also be greater thanz. - Inside the loop for
x, start another loop foryfrom 1 to 1000. - Calculate
val = customfunction.f(x, y). - If
val == z, add the pair[x, y]to theresultlist. Sincefis strictly increasing withy, we can break the inner loop and continue with the nextx. - If
val > z, we can break the inner loop fory. Because the function is monotonically increasing,customfunction.f(x, y+1)will also be greater thanz. - If
val < z, continue the inner loop to check the nexty. - After the loops complete, return the
resultlist.
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
zis large.The worst-case time complexity is quadratic, which is significantly slower than other available methods.
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.
Algorithm
- Initialize an empty list
result. - Iterate through
xfrom 1 to 1000. - For each
x, the functiong(y) = f(x, y)is a monotonically increasing function ofy. We can use binary search to find ayin the range[1, 1000]such thatg(y) == z. - Set up binary search pointers
low = 1andhigh = 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 currentx(sinceymust be unique for a givenx). - If
val < z, we need a larger value, so we search in the upper half by settinglow = mid + 1. - If
val > z, we need a smaller value, so we search in the lower half by settinghigh = mid - 1.
- Calculate
- Return the
resultlist.
Walkthrough
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.
/* * // 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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Visualize the
(x, y)pairs and their function valuesf(x, y)as a 2D matrix that is sorted row-wise and column-wise. - Initialize two pointers:
x = 1(starting from the first column) andy = 1000(starting from the last row). - Initialize an empty list
result. - Loop as long as
x <= 1000andy >= 1:- Calculate
val = customfunction.f(x, y). - If
val == z, a solution is found. Add[x, y]toresult. To find other potential solutions, we must move to a different state. We incrementxand decrementyto continue the search. - If
val < z, we need a larger value. Sincef(x, y)increases withx, we incrementxtox+1. - If
val > z, we need a smaller value. Sincef(x, y)increases withy, we decrementytoy-1.
- Calculate
- Return the
resultlist.
Walkthrough
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. Sincexis already at its minimum, we can only decreasey. This effectively eliminates the entire rowyfrom 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 increasex, which effectively eliminates the columnxfrom 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 > 1000ory < 1), having covered the entire search space in linear time.
/* * // 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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
/* * // 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 ; } }/* * // 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 ; } };""" 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 ansVideo 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.