A little explanation on GCD method. C++/Java/Python


  • 65

    only thing we should proof is this:

    if x and y are coprime,  then we can and only can reach every integer z in [0, x + y]. (1)
    

    then for a GCD g, from gx and gy,
    we can and only can reach every z in {i * g | i in [0, x + y] }

    now, let's see how to proof (1).
    let x be the less one, and y the greater one.
    then fill the two jug to full, we have x and y water each and x + y water in total.
    then we pour out x water each time until we can't.

    now we have these different z:

     y + x,  y,  y - x,  y - 2x, ... , y % x 
    

    finally we have y % x water left, we pour it into the x jug,
    then fill the y jug to full.
    now the two jugs have y % x and y water separately,
    and y + y % x water in total.
    then we pour from y jug into x jug until the x jug is full,
    afterwards do the same thing like before,
    to pour out x water each time until we can't.

    finally we get (y + y % x) % x = (y % x + y % x) % x = (2y) % x water left.

    now we have these different z:

     y + y % x,   y + y % x - x,  y + y % x - 2x, ... ,  (2y) % x 
    

    do this x times, we get z:

     y + (2y) % x,  y + (2y) % x - x, y + (2y) % x - 2x, ..., (3y) % x
     :
     :
     :    
     y + ((x-1)y) % x,  y + ((x-1)y) % x - x,  y + ((x-1)y) % x - 2x, ... ,  (xy) % x
    

    then you see (xy) % x = 0, and

    set { y % x, (2y) % x, (3y) % x, ... , ((x-1)y) % x } just equals to { 1, 2, 3, 4, 5, ... , x - 1 } . (2)

    proof for (2):
    modulo x could get x - 1 different results at most exclusive 0, that's 1,2,3,...,x-1.
    we have x - 1 expressions, suppose there is two same,
    let a != b in [1, x-1] and (ay) % x = (by) % x,
    then we get ((a - b)y) % x = 0,
    then ((a - b) % x) * (y % x) = 0, (a - b) % x = 0.
    for 1 <= a, b <= x - 1, so we get a = b. it's impossible.

    so we can get any z in [0, x + y] water for coprime x and y.

    C++ code:

    bool canMeasureWater(int x, int y, int z) {
        return z == 0 || z <= (long long)x + y && z % __gcd(x, y) == 0;
    }
    

    Java code:

    public boolean canMeasureWater(int x, int y, int z) {
        return z == 0 || (long)x + y >= z && z % gcd(x, y) == 0;
    }
    public int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    

    Python code:

    def canMeasureWater(self, x, y, z):
        from fractions import gcd
        return z == 0 or x + y >= z and z % gcd(x, y) == 0
    

    p.s. the testcases are too weak.
    you may get overflow without long long, say 2147483647, 234524287, 1.
    some code get AC, while runs wrong on this 4,6,8.


  • 0
    L

    Thanks for your clear explanation and code.


  • 0
    Z

    Great explanation! Thanks a lot!


  • 1

    @ShuangquanLi
    Good explanation Here is my iteration version.

    def canMeasureWater(self, x, y, z):
            gcd, r = max(x, y), min(x, y)
            while r: gcd, r = r, gcd % r
            return z == 0 or x + y >= z and z % gcd == 0

  • 0
    A

    Thanks for your elegant explanation. But, I am a little confused how do you proof that if the GCD cannot divide z, there must have no solution. From your strategy, you show that if if the GCD divides z, there must have a solution. And there is not solution if the GCD cannot divide z when following your strategy. Your strategy is very clever because you check the situation only at the end of each inner loop, which avoids many mess. But is there a possibility that we can construct a solution using another strategy rather than always fill y and empty x iteratively?


  • 0
    A

    I know how to proof................it is so easy!!!!!
    I define jugs 3 states: full, part and empty.
    the key lemma is :

    after any steps, there is at most one jug is in part state

    proof:
    we have 3 operations available:

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

    only the third one can lead to a part state.

    • if the filled jug is in part state, the filling jug must be empty
    • if the filling jug is in part state, the filled jug must be full

    Then we can use induction to proof :

    after any steps, the total water in the two jugs must be a multiple of GCD(x, y)


  • 0
    H

    Hi, I just confuse when x and y are not coprime, how to deal with it? Can anyone help?


  • 0
    A

    @hangdu do you see my proof above? I prove that total water in both jugs must be a multiple of GCD(x, y) after any operations no matter how you fill and pour. And the original author gives a way to get any multiple of GCD(x, y) water.
    which means that as long as the requested water is a multiple of GCD(x, y), we can construct it! And if the requested water is not a multiple of GCD(x, y), there must have no solution.


Log in to reply
 

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