Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1237.html
1237. Find Positive Integer Solution for a Given Equation (Easy)
Given a function f(x, y)
and a value z
, return all positive integer pairs x
and y
where f(x,y) == z
.
The function is constantly 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 positive integer f(x, y) for any given positive integer x and y. int f(int x, int y); };
For custom testing purposes you're given an integer function_id
and a target z
as input, where function_id
represent one function from an secret internal list, on the examples you'll know only two functions from the list.
You may return the solutions in any order.
Example 1:
Input: function_id = 1, z = 5 Output: [[1,4],[2,3],[3,2],[4,1]] Explanation: function_id = 1 means that f(x, y) = x + y
Example 2:
Input: function_id = 2, z = 5 Output: [[1,5],[5,1]] Explanation: function_id = 2 means that f(x, y) = x * y
Constraints:
1 <= function_id <= 9
1 <= z <= 100
- It's guaranteed that the solutions of
f(x, y) == z
will be on the range1 <= x, y <= 1000
- It's also guaranteed that
f(x, y)
will fit in 32 bit signed integer if1 <= x, y <= 1000
Related Topics:
Math, Binary Search
Solution 1. Brute Force
// OJ: https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& func, int z) {
vector<vector<int>> ans;
for (int x = 1; x <= 1000; ++x) {
for (int y = 1; y <= 1000; ++y) {
if (func.f(x, y) == z) ans.push_back({ x, y });
}
}
return ans;
}
};
Solution 2. Binsary Search
// OJ: https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& func, int z) {
vector<vector<int>> ans;
for (int x = 1; x <= 1000; ++x) {
int L = 1, R = 1000;
while (L <= R) {
int y = (L + R) / 2, val = func.f(x, y);
if (val == z) {
ans.push_back({ x, y });
break;
} else if (val < z) L = y + 1;
else R = y - 1;
}
}
return ans;
}
};
Solution 3. Two Pointers
// OJ: https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& func, int z) {
vector<vector<int>> ans;
for (int x = 1, y = 1000; x <= 1000 && y >= 1; ++x) {
while (y >= 1 && func.f(x, y) > z) --y;
if (y >= 1 && func.f(x, y) == z) ans.push_back({ x, y });
}
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) * public int f(int x, int y); * }; */ class Solution { public List<List<Integer>> findSolution(CustomFunction customfunction, int z) { List<List<Integer>> solutions = new ArrayList<List<Integer>>(); for (int x = 1; x <= 1000; x++) { for (int y = 1; y <= 1000; y++) { int function = customfunction.f(x, y); if (function >= z) { if (function == z) { List<Integer> solution = new ArrayList<Integer>(); solution.add(x); solution.add(y); solutions.add(solution); } break; } } } return 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<>(); int x = 1, y = 1000; while (x <= 1000 && y > 0) { int t = customfunction.f(x, y); if (t < z) { x++; } else if (t > z) { y--; } else { ans.add(Arrays.asList(x++, y--)); } } return ans; } }
-
// OJ: https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/ // Time: O(N^2) // Space: O(1) class Solution { public: vector<vector<int>> findSolution(CustomFunction& func, int z) { vector<vector<int>> ans; for (int x = 1; x <= 1000; ++x) { for (int y = 1; y <= 1000; ++y) { if (func.f(x, y) == z) ans.push_back({ x, y }); } } 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]]: res = [] for x in range(1, 1001): left, right = 1, 1000 while left < right: mid = (left + right) >> 1 if customfunction.f(x, mid) >= z: right = mid else: left = mid + 1 if customfunction.f(x, left) == z: res.append([x, left]) return res ############ # 1237. Find Positive Integer Solution for a Given Equation # https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/ """ 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]]: y = 1000 res = [] for x in range(1,1000): while y > 1 and customfunction.f(x,y) > z: y -= 1 if customfunction.f(x,y) == z: res.append([x,y]) return res
-
/** * 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 }
-
/** * // 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; }