Find Positive Integer Solution for a Given Equation

Find Positive Integer Solution for a Given Equation - 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.

Input & Output

Example 1 — Simple Addition Function

$ Input: function_id = 1, z = 5

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

💡 Note: Assuming f(x,y) = x + y, we need pairs where x + y = 5. Valid positive integer pairs are (1,4), (2,3), (3,2), (4,1).

Example 2 — Product Function

$ Input: function_id = 2, z = 6

› Output: [[1,6],[2,3],[3,2],[6,1]]

💡 Note: Assuming f(x,y) = x * y, we need pairs where x * y = 6. Valid positive integer pairs are (1,6), (2,3), (3,2), (6,1).

Example 3 — Large Target

$ Input: function_id = 1, z = 100

› Output: [[1,99],[2,98],...[99,1]]

💡 Note: For f(x,y) = x + y with target 100, there are 99 valid pairs from (1,99) to (99,1).

Constraints

The function f is defined for you
1 ≤ z ≤ 100
It's guaranteed that the solutions of f(x, y) == z will be on the range 1 ≤ x, y ≤ 1000
It's also guaranteed that f(x, y) will fit in 32-bit signed integer if 1 ≤ x, y ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Hidden monotonic function f(x,y) and target value z

Process

Search grid efficiently using monotonic property

Output

All positive integer pairs where f(x,y) = z

Key Takeaway

🎯 Key Insight: The monotonic property allows us to eliminate entire rows/columns during search, making the solution much more efficient than brute force

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is leveraging the monotonically increasing property of the function to eliminate large search spaces efficiently. The two-pointer approach is optimal, starting from a corner and navigating based on comparison results. Time: O(x + y), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Y	O(x log y)	O(k)	For each x, binary search to find y values where f(x,y) equals z
Two Pointers	O(x + y)	O(k)	Start from corners and use monotonic property to navigate efficiently
Brute Force	O(n²)	O(k)	Test all possible (x, y) pairs within reasonable bounds

Binary Search on Y — Algorithm Steps

Iterate through possible x values
For each x, binary search on y to find f(x,y) = z
Collect all valid (x,y) pairs
Stop when f(x,1) > z since larger x won't work

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix X

For each x, binary search on y dimension

Binary Search

Use monotonic property to search efficiently

Find Match

Locate exact y where f(x,y) = z

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int mock_f(int x, int y) {
    return x + y;
}

void solution(int (*f)(int, int), int z) {
    int result[10000][2];
    int count = 0;
    
    for (int x = 1; x <= 1000; x++) {
        if (f(x, 1) > z) {
            break;
        }
        
        int left = 1, right = 1000;
        while (left <= right) {
            int mid = (left + right) / 2;
            int val = f(x, mid);
            
            if (val == z) {
                result[count][0] = x;
                result[count][1] = mid;
                count++;
                break;
            } else if (val < z) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
}

int main() {
    int functionId, z;
    scanf("%d %d", &functionId, &z);
    
    solution(mock_f, z);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(x log y)

For each x value, perform binary search on y which takes O(log y) time

⚡ Linearithmic

Space Complexity

O(k)

Only store the result pairs, where k is the number of valid solutions

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Y — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler