No tricky maths, no GCD, O(1) space, C++ solution with explanation


  • 3

    To make it convenient, we can always let x be the smaller jug and y be the larger jug. Then we can use the current water amount in y to see if it can measure z.

    Example:
    Input: x = 3, y = 5, z = 4

    Operations allowed:
    (1) Fill any of the jugs completely with water.
    (2) Empty any of the jugs.
    (3) Pour water from one jug into another till the other jug is completely full.
    (4) Pour water from one jug into another till the first jug itself is empty.

    First, let two jugs both have x liters which is 3.
    jugX: 3 jugY: 3

    As jugY has a total capacity of 5, we can pour 2 from jug x to y.
    jugX: 1 jugY: 5

    And jug y is full, we should empty jug y to carry on measuring.
    jugX: 1 jugY: 0

    Pour 1 from jug x to y.
    jugX: 0 jugY: 1

    Now jug x is empty, we need to refill jug x to move on.
    jugX: 3 jugY: 1

    Jug y has enough space for jug x to pour all its water in, then do it.
    jugX: 0 jugY: 4

    Right, we notice that we can measure z = 4 here using jug y, we should stop and return true. But we can do it further to see the "rule".
    jugX: 3 jugY: 4
    jugX: 2 jugY: 5
    jugX: 2 jugY: 0
    jugX: 0 jugY: 2
    jugX: 3 jugY: 2 <--pay attention
    jugX: 0 jugY: 5
    jugX: 0 jugY: 0
    jugX: 3 jugY: 3 <--pay attention
    ...

    Can you notice that? We come to the initial setting of two jugs and go into a cycle. We can stop at the first "pay attention" step because this step will lead to the result of two empty jugs. The condition is:
    jug y's total capacity - current water amount in y = current water amount in jug x

    So the worst case is that we go through one cycle and find that we cannot measure z, then we should return false.

    That's the main idea of this algorithm. Besides, we need to consider some special cases. We can first judge if x = z or y = z or x + y = z. And...yes, during pouring water from one jug to the other one, we also need to see if current water in jug x + current water in y = z.

    Now I think you can understand my code ;P

    class Solution {
    public:
        bool canMeasureWater(int x, int y, int z) {
            if (x > y) swap(x, y);
            if (x == z || y == z || x + y == z) return true;   //specific cases
            int currX = x;   //current water amount in smaller jug
            int currY = x;   //current water amount in larger jug
            if (x != 0 && y != 0) {
                while (1) {
                    if (currY == z || currX + currY == z) return true;
                    if (y - currY == currX) break;
                    else if (y - currY > currX) {
                        currY = currY + currX;
                        currX = x;
                    }
                    else {
                        currX = currX - (y - currY);
                        currY = 0;
                    }
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.