-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1237-FindPositiveIntegerSolutionForAGivenEquation.cs
121 lines (102 loc) · 3.38 KB
/
1237-FindPositiveIntegerSolutionForAGivenEquation.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//-----------------------------------------------------------------------------
// Runtime: 196ms
// Memory Usage: 25.6 MB
// Link: https://leetcode.com/submissions/detail/330138747/
//-----------------------------------------------------------------------------
using System;
using System.Collections.Generic;
namespace LeetCode
{
/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* public 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);
* };
*/
public class _1237_FindPositiveIntegerSolutionForAGivenEquation
{
public IList<IList<int>> FindSolution(CustomFunction customfunction, int z)
{
var solutions = new List<IList<int>>();
int minX = MinX(customfunction, z);
int maxX = MaxX(customfunction, z);
for (int x = minX; x <= maxX; x++)
{
var solution = BinarySearchY(customfunction, x, z);
if (solution != null)
solutions.Add(solution);
}
return solutions;
}
private int MinX(CustomFunction customfunction, int z)
{
int min = 1;
int max = 1000;
while (min <= max)
{
int mid = (min + max) / 2;
int fMid = customfunction.f(mid, 1000);
if (fMid == z)
return mid;
if (fMid < z)
min = mid + 1;
else
max = mid - 1;
}
return min;
}
private int MaxX(CustomFunction customfunction, int z)
{
int min = 1;
int max = 1000;
while (min <= max)
{
int mid = (min + max) / 2;
int fMid = customfunction.f(mid, 1);
if (fMid == z)
return mid;
if (fMid < z)
min = mid + 1;
else
max = mid - 1;
}
return max;
}
private IList<int> BinarySearchY(CustomFunction customfunction, int x, int z)
{
int min = 1;
int max = 1000;
while (min <= max)
{
int mid = (min + max) / 2;
int fMid = customfunction.f(x, mid);
if (fMid == z)
return new int[] { x, mid };
if (fMid < z)
min = mid + 1;
else
max = mid - 1;
}
return null;
}
public class CustomFunction
{
private Func<int, int, int> func;
public CustomFunction(Func<int, int, int> func)
{
this.func = func;
}
// 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)
{
return func(x, y);
}
};
}
}