_1237.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.List;

publicclass_1237 {

// This is the custom function interface.
// You should not implement it, or speculate about its implementation
abstractclassCustomFunction {
// 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)
publicabstractintf(intx, inty);
 }

publicstaticclassSolution1 {
/*
 * Time: O(x*y)
 * Space: O(1)
 */
publicList<List<Integer>> findSolution(CustomFunctioncustomfunction, intz) {
List<List<Integer>> result = newArrayList<>();
for (intx = 1; x <= 1000; x++) {
for (inty = 1; y <= 1000; y++) {
if (customfunction.f(x, y) == z) {
result.add(Arrays.asList(x, y));
 }
 }
 }
returnresult;
 }
 }

publicstaticclassSolution2 {
/*
 * linear search
 * <p>
 * Time: O(x + y)
 * Space: O(1)
 */
publicList<List<Integer>> findSolution(CustomFunctioncustomfunction, intz) {
List<List<Integer>> result = newArrayList<>();
intx = 1;
inty = 1000;
while (x < 1001 && y > 0) {
intfunctionResult = customfunction.f(x, y);
if (functionResult < z) {
x++;
 } elseif (functionResult > z) {
y--;
 } else {
result.add(Arrays.asList(x++, y--));
 }
 }
returnresult;
 }
 }

publicstaticclassSolution3 {
/*
 * binary search
 * <p>
 * Time: O(xlogy)
 * Space: O(1)
 */
publicList<List<Integer>> findSolution(CustomFunctioncustomfunction, intz) {
List<List<Integer>> result = newArrayList<>();
for (intx = 1; x <= 1000; x++) {
intleft = 1;
intright = 1001;
while (left < right) {
inty = (left + right) / 2;
if (customfunction.f(x, y) < z) {
left = y + 1;
 } else {
right = y;
 }
 }
if (customfunction.f(x, left) == z) {
result.add(Arrays.asList(x, left));
 }
 }
returnresult;
 }
 }
}