Leetcode 365. Water and Jug Problem


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.

Operations allowed:

  • Fill any of the jugs completely.
  • 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.



目前尚存在争议的一个问题是在最后量取的步骤中水壶能否被多次使用(比如x=1, y=2, z=5的情况,是否可以用1+2+2=5来实现),该问题的讨论区里也在讨论中。目前的test cases好像是认定为最终只能用两个水壶在某一时刻里存有的总水量来衡量,所以z>x+y的情况都判定为false了。


class Solution {
    int gcd(int x, int y)  
        return y==0?x:gcd(y, x%y);  
    bool canMeasureWater(int x, int y, int z) {
        if(z < 0 || z > x + y)
            return false;
        if(z % gcd(x, y))
            return false;
            return true;

Leave a Reply