C++ solution with simple explanation of the strategy (no math/GCD)

  • 0

    Idea is to pour from larger jug to smaller jug repeatedly until one of the jogs or both reach the target.

    class Solution {
        bool canMeasureWater(int x, int y, int z) {
            if(z==0) return true;
            // make x the smaller value
                int temp=x;
            int xCapacity=x;
            int yCapacity=y;
            map<int,bool> encountered; // map to track if we have encountered this jug quantity before.
            x=0; y=yCapacity; // empty x and fill y
            // Lets start!
                // the amount you can pour from y to x is the amount of empty space in x, or the entire contents of y, whichever is lesser.
                int pourOutFromYtoX = min(xCapacity-x, y); 
                x += pourOutFromYtoX; // pour into x
                y -= pourOutFromYtoX; // pour out of y
                // Did we reach our target in any of the jogs or both?
                if(y==z || x==z || y+x==z) return true;
                // Did we encounter the contents of y before? Then this is an infinite loop, so exit
                if(encountered.find(y) != encountered.end()) return false;
                // if contents of y are more than xCapacity, then re-use the contents of y because you can max out x in the next iteration w/o refilling y; else refill y to its full capacity.
                if(y > xCapacity)
                    x=0; // throw away x and restart with existing y;
                    x=y; // pour out y into x;
                    y=yCapacity; // refill y with full capacity
            return false;

Log in to reply

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