-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
365.java
49 lines (45 loc) · 1.4 KB
/
365.java
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
__________________________________________________________________________________________________
sample 0 ms submission
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if(x + y < z) return false;
//case x or y is zero
if( x == z || y == z || x + y == z ) return true;
//get GCD, then we can use the property of Bézout's identity
return z%GCD(x, y) == 0;
}
public int GCD(int a, int b){
while(b != 0 ){
int temp = b;
b = a%b;
a = temp;
}
return a;
}
}
__________________________________________________________________________________________________
sample 31456 kb submission
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (z > x + y) return false;
if (z == x || z == y) return true;
int a = Math.max(x,y);
int b = Math.min(x,y);
int gcd = findGcd(a,b);
System.out.println(gcd);
return ((y!= 0) && z % y == 0) || ((x != 0) && z % x == 0) || ((x!= 0 && y != 0 && z % gcd == 0));
}
public static int findGcd(int a, int b){
if (a == b) return a;
int gcd = 1;
for (int i = 2; i <= b; i++){
while (a % i == 0 && b % i == 0){
gcd *= i;
a /= i;
b /= i;
}
}
return gcd;
}
}
__________________________________________________________________________________________________