Question
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:
- Fill any of the jugs completely with water.
- Empty any of the jugs.
- Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
Code
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (z == x || z == y) return true;
if (z > (x + y)) return false;
int n = get(x, y);
if (n == 0) return false;
return z % n == 0;
}
public int get(int a, int b) {//求最大公约数
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}
Solution
z不能超过x与y之和。
若z等于x或y则肯定可以完成要求。
若z是x与y的最大公约数的倍数，也可以完成要求。
