1237. Find Positive Integer Solution for Equation

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

Approach overview

Problem Overview: You are given a hidden monotonic function f(x, y) and an integer z. The goal is to find all positive integer pairs (x, y) such that f(x, y) = z. The function increases as either x or y increases, which guarantees ordered behavior that can be exploited for faster search.

Approach 1: Brute-force Search Method (O(n^2) time, O(1) space)

The most direct solution checks every possible pair (x, y) within the valid range (typically 1 ≤ x, y ≤ 1000). For each pair, call the provided API f(x, y) and compare the result with z. If the result matches, store the pair. This approach works because the search space is bounded, but it performs up to one million function calls. While acceptable for small limits, it ignores the key property of the function: monotonic growth. Use this approach mainly to verify correctness or when constraints are extremely small.

Approach 2: Two-pointer Approach (O(n) time, O(1) space)

The function increases with both variables. That means if f(x, y) is too large, increasing y further will only increase the value. This monotonic property allows a classic two pointers strategy. Start with x = 1 and y = 1000. Compute f(x, y). If the value equals z, record the pair and move both pointers (x++, y--) to continue searching. If the value is smaller than z, increase x to raise the function value. If it is larger than z, decrease y. Each step eliminates an entire row or column of the search grid, reducing the complexity to linear time. This pattern frequently appears in problems combining math properties with ordered search.

Another valid variation uses binary search: for each fixed x, binary search the value of y that satisfies f(x, y) = z. That runs in O(n log n), but the two-pointer scan is simpler and faster.

Recommended for interviews: The two-pointer approach is what interviewers typically expect. It demonstrates that you recognized the monotonic behavior of the function and converted a quadratic search into a linear scan. Showing the brute-force method first proves baseline reasoning, but switching to the optimized two-pointer solution highlights algorithmic thinking and pattern recognition.

Approach 1: Brute-force Search Method

The simplest approach is to iterate through all possible values of x and y within the given constraints. For every x (from 1 to 1000), calculate the corresponding y such that f(x, y) == z. Since the function f(x, y) is monotonically increasing, this method will eventually find all pairs that satisfy the condition. This is a brute-force method and is not the most efficient due to its O(n^2) time complexity.

Python

class CustomFunction:
    def f(self, x, y):
        return x + y  # Example implementation

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int):
        solutions = []
        for x in range(1, 1001):
            for y in range(1, 1001):
                if customfunction.f(x, y) == z:
                    solutions.append([x, y])
                if customfunction.f(x, y) > z:
                    break
        return solutions

# Example usage
customfunction = CustomFunction()
solution = Solution()
print(solution.findSolution(customfunction, 5))

Java

import java.util.ArrayList;
import java.util.List;

// Placeholder for the CustomFunction
class CustomFunction {
    public int f(int x, int y) {
        return x + y; // Example function
    }
}

public class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> solutions = new ArrayList<>();
        for (int x = 1; x <= 1000; x++) {
            for (int y = 1; y <= 1000; y++) {
                if (customfunction.f(x, y) == z) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(x);
                    pair.add(y);
                    solutions.add(pair);
                }
                if (customfunction.f(x, y) > z) {
                    break;
                }
            }
        }
        return solutions;
    }

    public static void main(String[] args) {
        CustomFunction cf = new CustomFunction();
        Solution s = new Solution();
        List<List<Integer>> sols = s.findSolution(cf, 5);
        for (List<Integer> pair : sols) {
            System.out.println(pair);
        }
    }
}

C++

#include <iostream>
#include <vector>

// Placeholder for the CustomFunction
class CustomFunction {
public:
    int f(int x, int y) {
        return x + y; // Example function
    }
};

std::vector<std::pair<int, int>> findSolution(CustomFunction& customfunction, int z) {
    std::vector<std::pair<int, int>> solutions;
    for (int x = 1; x <= 1000; ++x) {
        for (int y = 1; y <= 1000; ++y) {
            if (customfunction.f(x, y) == z) {
                solutions.emplace_back(x, y);
            }
            if (customfunction.f(x, y) > z) {
                break;
            }
        }
    }
    return solutions;
}

int main() {
    CustomFunction cf;
    auto solutions = findSolution(cf, 5);
    for (auto& sol : solutions) {
        std::cout << "[" << sol.first << ", " << sol.second << "]\n";
    }
    return 0;
}

JavaScript

class CustomFunction {
    f(x, y) {
        return x + y; // Example function
    }
}

function findSolution(customfunction, z) {
    let solutions = [];
    for (let x = 1; x <= 1000; x++) {
        for (let y = 1; y <= 1000; y++) {
            if (customfunction.f(x, y) === z) {
                solutions.push([x, y]);
            }
            if (customfunction.f(x, y) > z) {
                break;
            }
        }
    }
    return solutions;
}

// Example usage
let customFunction = new CustomFunction();
console.log(findSolution(customFunction, 5));

#include <stdio.h>

// Placeholder for the CustomFunction
int f(int x, int y);

void findSolution(int z) {
    for (int x = 1; x <= 1000; ++x) {
        for (int y = 1; y <= 1000; ++y) {
            if (f(x, y) == z) {
                printf("[%d, %d]\n", x, y);
            }
            if (f(x, y) > z) {
                break;
            }
        }
    }
}

// Example use
int f(int x, int y) {
    return x + y;
}

int main() {
    findSolution(5);
    return 0;
}

using System;
using System.Collections.Generic;

public class CustomFunction
{
    public int F(int x, int y)
    {
        return x + y; // Example function
    }
}

public class Solution
{
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z)
    {
        IList<IList<int>> solutions = new List<IList<int>>();
        for (int x = 1; x <= 1000; x++)
        {
            for (int y = 1; y <= 1000; y++)
            {
                if (customfunction.F(x, y) == z)
                {
                    solutions.Add(new List<int> { x, y });
                }
                if (customfunction.F(x, y) > z)
                {
                    break;
                }
            }
        }
        return solutions;
    }

    static void Main()
    {
        var customFunction = new CustomFunction();
        var solution = new Solution();
        var results = solution.FindSolution(customFunction, 5);
        foreach (var pair in results)
        {
            Console.WriteLine($"[{pair[0]}, {pair[1]}]");
        }
    }
}

This Python code creates a class CustomFunction to mimic the hidden function. The function findSolution in the Solution class iterates over potential x, y pairs, checks for a match, and stores valid pairs in a list. Early stopping is implemented inside the loop when f(x, y) > z.

Complexity

Time Complexity: O(n^2), where n is the maximum bound (1000).
Space Complexity: O(m), where m is the number of solutions found.

Try this approach in the editor

Approach 2: Two-pointer Approach

Given that the function is monotonically increasing, an efficient approach involves using two pointers. Start one pointer at the beginning of a range (say x from 1 to 1000) and the other at the end (y starting from 1000). Adjust the pointers based on the result of f(x, y) compared to z. If f(x, y) > z, decrement y, else increment x. Keep adjusting until all solutions are found.

Python

class CustomFunction:
    def f(self, x, y):
        return x + y  # Example implementation

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int):
        solutions = []
        x, y = 1, 1000
        while x <= 1000 and y >= 1:
            result = customfunction.f(x, y)
            if result == z:
                solutions.append([x, y])
                x += 1
                y -= 1
            elif result < z:
                x += 1
            else:
                y -= 1
        return solutions

# Example usage
customfunction = CustomFunction()
solution = Solution()
print(solution.findSolution(customfunction, 5))

Java

import java.util.ArrayList;
import java.util.List;

// Placeholder for the CustomFunction
class CustomFunction {
    public int f(int x, int y) {
        return x + y; // Example function
    }
}

public class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> solutions = new ArrayList<>();
        int x = 1, y = 1000;
        while (x <= 1000 && y >= 1) {
            int result = customfunction.f(x, y);
            if (result == z) {
                List<Integer> pair = new ArrayList<>();
                pair.add(x);
                pair.add(y);
                solutions.add(pair);
                x++; y--;
            } else if (result < z) {
                x++;
            } else {
                y--;
            }
        }
        return solutions;
    }

    public static void main(String[] args) {
        CustomFunction cf = new CustomFunction();
        Solution s = new Solution();
        List<List<Integer>> sols = s.findSolution(cf, 5);
        for (List<Integer> pair : sols) {
            System.out.println(pair);
        }
    }
}

C++

#include <iostream>
#include <vector>

// Placeholder for the CustomFunction
class CustomFunction {
public:
    int f(int x, int y) {
        return x + y; // Example function
    }
};

std::vector<std::pair<int, int>> findSolution(CustomFunction& customfunction, int z) {
    std::vector<std::pair<int, int>> solutions;
    int x = 1, y = 1000;
    while (x <= 1000 && y >= 1) {
        int result = customfunction.f(x, y);
        if (result == z) {
            solutions.emplace_back(x, y);
            x++;
            y--;
        } else if (result < z) {
            x++;
        } else {
            y--;
        }
    }
    return solutions;
}

int main() {
    CustomFunction cf;
    auto solutions = findSolution(cf, 5);
    for (auto& sol : solutions) {
        std::cout << "[" << sol.first << ", " << sol.second << "]\n";
    }
    return 0;
}

JavaScript

class CustomFunction {
    f(x, y) {
        return x + y; // Example function
    }
}

function findSolution(customfunction, z) {
    let solutions = [];
    let x = 1, y = 1000;
    while (x <= 1000 && y >= 1) {
        let result = customfunction.f(x, y);
        if (result === z) {
            solutions.push([x, y]);
            x++;
            y--;
        } else if (result < z) {
            x++;
        } else {
            y--;
        }
    }
    return solutions;
}

// Example usage
let customFunction = new CustomFunction();
console.log(findSolution(customFunction, 5));

#include <stdio.h>

// Placeholder for the CustomFunction
int f(int x, int y);

void findSolution(int z) {
    for (int x = 1, y = 1000; x <= 1000 && y >= 1; ) {
        int result = f(x, y);
        if (result == z) {
            printf("[%d, %d]\n", x, y);
            x++; y--; // Move both pointers
        } else if (result < z) {
            x++; // Increase x to increase f(x, y)
        } else {
            y--; // Decrease y to decrease f(x, y)
        }
    }
}

// Example use
int f(int x, int y) {
    return x + y;
}

int main() {
    findSolution(5);
    return 0;
}

using System;
using System.Collections.Generic;

public class CustomFunction
{
    public int F(int x, int y)
    {
        return x + y; // Example function
    }
}

public class Solution
{
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z)
    {
        IList<IList<int>> solutions = new List<IList<int>>();
        int x = 1, y = 1000;
        while (x <= 1000 && y >= 1)
        {
            int result = customfunction.F(x, y);
            if (result == z)
            {
                solutions.Add(new List<int> { x, y });
                x++; y--;
            }
            else if (result < z)
            {
                x++;
            }
            else
            {
                y--;
            }
        }
        return solutions;
    }

    static void Main()
    {
        var customFunction = new CustomFunction();
        var solution = new Solution();
        var results = solution.FindSolution(customFunction, 5);
        foreach (var pair in results)
        {
            Console.WriteLine($"[{pair[0]}, {pair[1]}]");
        }
    }
}

In Python, a similar two-pointer approach is applied, with pointers at the start and end of the range. Adjust movement of either x or y until all valid pairs fulfilling f(x, y) == z are discovered, using space proportionate to discovered solutions.

Complexity

Time Complexity: O(n), where n is the range (1000).
Space Complexity: O(m), where m is the number of solutions found.

Try this approach in the editor

Approach 3: Enumeration + Binary Search

According to the problem, we know that the function f(x, y) is a monotonically increasing function. Therefore, we can enumerate x, and then binary search y in [1,...z] to make f(x, y) = z. If found, add (x, y) to the answer.

The time complexity is O(n log n), where n is the value of z, and the space complexity is O(1).

TypeScript

/**
 * // This is the CustomFunction's API interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *      f(x: number, y: number): number {}
 * }
 */

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    const ans: number[][] = [];
    for (let x = 1; x <= 1000; ++x) {
        let l = 1;
        let r = 1000;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (customfunction.f(x, mid) >= z) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (customfunction.f(x, l) == z) {
            ans.push([x, l]);
        }
    }
    return ans;
}

/**
 * This is the declaration of customFunction API.
 * @param  x    int
 * @param  x    int
 * @return 	    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)
 */

func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
	for x := 1; x <= 1000; x++ {
		y := 1 + sort.Search(999, func(y int) bool { return customFunction(x, y+1) >= z })
		if customFunction(x, y) == z {
			ans = append(ans, []int{x, y})
		}
	}
	return
}

Try this approach in the editor

Approach 4: Two Pointers

We can define two pointers x and y, initially x = 1, y = z.

If f(x, y) = z, we add (x, y) to the answer, then x \leftarrow x + 1, y \leftarrow y - 1;
If f(x, y) \lt z, at this time for any y' \lt y, we have f(x, y') \lt f(x, y) \lt z, so we cannot decrease y, we can only increase x, so x \leftarrow x + 1;
If f(x, y) \gt z, at this time for any x' \gt x, we have f(x', y) \gt f(x, y) \gt z, so we cannot increase x, we can only decrease y, so y \leftarrow y - 1.

After the loop ends, return the answer.

The time complexity is O(n), where n is the value of z, and the space complexity is O(1).

TypeScript

/**
 * // This is the CustomFunction's API interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *      f(x: number, y: number): number {}
 * }
 */

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    let x = 1;
    let y = 1000;
    const ans: number[][] = [];
    while (x <= 1000 && y) {
        const t = customfunction.f(x, y);
        if (t < z) {
            ++x;
        } else if (t > z) {
            --y;
        } else {
            ans.push([x--, y--]);
        }
    }
    return ans;
}

/**
 * This is the declaration of customFunction API.
 * @param  x    int
 * @param  x    int
 * @return 	    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)
 */

func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
	x, y := 1, 1000
	for x <= 1000 && y > 0 {
		t := customFunction(x, y)
		if t < z {
			x++
		} else if t > z {
			y--
		} else {
			ans = append(ans, []int{x, y})
			x, y = x+1, y-1
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute-force Search Method	Time Complexity: O(n^2), where n is the maximum bound (1000). Space Complexity: O(m), where m is the number of solutions found.
Two-pointer Approach	Time Complexity: O(n), where n is the range (1000). Space Complexity: O(m), where m is the number of solutions found.
Enumeration + Binary Search	–
Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Brute-force Search	O(n^2)	O(1)	Useful for small bounds or validating logic when first approaching the problem.
Binary Search per x	O(n log n)	O(1)	Works when the function is strictly increasing in y for each fixed x.
Two-pointer Scan	O(n)	O(1)	Best choice when both variables produce monotonic increases, enabling elimination of rows or columns.

Frequently asked questions

Is Find Positive Integer Solution for a Given Equation easy or hard?

The problem is rated Medium on LeetCode. The challenge is recognizing that the custom function is strictly increasing, which allows replacing a naive O(n^2) search with a linear two-pointer scan.

Find Positive Integer Solution for a Given Equation Python/Java solution

In Python or Java, implement a loop with two pointers: x starting at 1 and y starting at 1000. Repeatedly call f(x, y) and adjust pointers depending on whether the result is less than, greater than, or equal to z. Store valid pairs in a result list.

How to solve Find Positive Integer Solution for a Given Equation in O(n)?

Use a two-pointer scan across the search grid. Start with x=1 and y=1000. If f(x,y) equals z, record the pair and move both pointers. If the value is smaller than z, increase x; if larger, decrease y. Each move removes a full row or column from consideration, producing O(n) complexity.

What is the best approach for Find Positive Integer Solution for a Given Equation?

The two-pointer approach is the optimal solution. Because the custom function f(x, y) increases as either x or y increases, you can start from (x=1, y=1000) and move pointers based on whether the computed value is smaller or larger than z. This reduces the search from O(n^2) to O(n).

Is Find Positive Integer Solution for a Given Equation asked at Google/Amazon/Meta?

Problems involving monotonic functions and two-pointer search patterns commonly appear in interviews at companies like Google, Amazon, and Meta. The question tests reasoning about ordered search spaces and reducing brute-force complexity.

What data structure is used in Find Positive Integer Solution for a Given Equation?

No specialized data structure is required. The solution mainly relies on pointer variables and repeated calls to the provided API function. The key concept is exploiting monotonic behavior rather than storing intermediate data.

What is the time complexity of Find Positive Integer Solution for a Given Equation?

The optimal two-pointer solution runs in O(n) time with O(1) extra space, where n is the maximum possible value of x or y (commonly 1000). A brute-force solution that checks every pair requires O(n^2) time.

Find Positive Integer Solution for a Given Equation solution and explanation

The problem

Approach overview

Approach 1: Brute-force Search Method

Approach 2: Two-pointer Approach

Approach 3: Enumeration + Binary Search

Approach 4: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Positive Integer Solution for a Given Equation solution and explanation

The problem

Approach overview

Approach 1: Brute-force Search Method

Approach 2: Two-pointer Approach

Approach 3: Enumeration + Binary Search

Approach 4: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems