share my simulated method with explanation, no math theory [c++]


  • 2
    Z

    In this method I use two loops to traverse all the possible values of z.
    When I tried to find all possible ways to pour,empty and fill water, no matter how I operated,eventually I would fall in these two loops' patterns. Actually I haven't tried to prove my conclusion, but I think the proving method should be similar to this GCD method,associated with Bézout's identity.
    For the first loop,we keep filling the smaller jug, pouring water from the smaller jug to the bigger jug, when the bigger jug is full, empty it, and pour all the remaining water(let's say it's t) from the smaller jug.Loop it until the value of t repeat once. It's not difficult to find that if z%x==t is satisfied,the answer is true. The first two rounds are shown below.
    0_1467551472922_Captu21re.PNG

    For the second loop,we keep filling the bigger jug, pouring water from the bigger jug to the smaller one and empty the smaller one,when the remaining water(t) in the bigger jug is less than the smaller jug's capacity,pour it to the smaller one.Loop it until the value of t repeat once.The satisfying condition is still z%x==t.

    bool canMeasureWater(int x, int y, int z) {
            if(z>x+y)return false;
            if(x>y)swap(x,y);
            if(!x){
                if(z&&z!=y) return false;
                else return true;
            }
            int pre1[x]={0},t=0;
            while(!(pre1[t]++)){
              if(t==z%x)return true;
              t=(y-x+t)%x;
            }
            t=x;
            int pre2[x+1]={0};
            while(!(pre2[t]++)){
                if(t==z%x)return true;
                t=x-(y-t)%x;
            }
            return false;
        }
    

  • 0

    @zoharlee said in share my simulated method with explanation, no math theory [c++]:

    Actually there are only two methods to get all the possible values of z

    I'd say there are infinitely many such methods. But more importantly: How do you know that your methods get all possible values?


  • 0
    Z

    Oh sorry,I have modified my explanation.Actually I can't prove it ,it's just two simple and general patterns I found after I tested as many ways as I can.


Log in to reply
 

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