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


  • 0
    A

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

    class Solution {
    public:
        bool canMeasureWater(int x, int y, int z) {
            if(z==0) return true;
            
            // make x the smaller value
            if(x>y){
                int temp=x;
                x=y;
                y=temp;
            }
            
            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!
            while(true)
            {
                // 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;
                encountered[y]=true;
                
                // 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;
                }
                else
                {
                    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.