Share my 0ms C++ solution with proof and explanation


  • 7
    K

    You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

    If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

    Operations allowed:

    • 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.

    Here I choose a math solution based on linear congruential formula:

    • ax ≡ b (mod n)

    Just take a try! (Example 1)

    We can write down all the possible x and y (start from x = 0, y = 0, end at x = 3, y = 5 ):

    • (0,0)
    • (0,5)
    • (3,2)
    • (0,2)
    • (2,0)
    • (2,5)
    • (3,4)
    • (0,4)
    • (3,1)
    • (0,1)
    • (1,0)
    • (1,5)
    • (3,3)
    • (0,3)
    • (3,0)
    • (3,3)
    • (3,5)

    If we put these points to a 2D oblique coordinate system (θ = 60°), and draw the paths from the start to the end. We can get

    path graph for example 1

    If you imagine that

    • The border lines (x = 0, y = 0, x = 3, y = 5) are mirrors
    • The start point (0,0) is a light source

    As the angle of incidence equals the angle of reflection, have you find that the route is light path diagram?

    In the diagram, EACH REFLECTION POINT is A SOLUTION FOR (x,y)

    Since what we need is the sum of x and y, note that:

    • RED route: x is same.
    • BLUE route: The value x + y of the start point is as same as the end point.
      - (2,5) to (3,4)
      - (1,5) to (3,3)
      - (0,5) to (3,2)
      - (0,4) to (3,1)
      - (0,3) to (3,0)
      - (0,2) to (2,0)
      - (0,1) to (1,0)
    • GREEN route: y is same.

    At first, I write a program to follow the light path diagram, but when x and y is too high, the program is slow.


    Let's make it more general!

    For normal y = p, x = q (p > q > 0), if we draw the paths (between 2 RED routes) in a 2D oblique coordinate system, we get

    general path graph

    As the sum x + y keep the same on the BLUE route, we ONLY focus on the points on the y-axis.

    • From A0, we get (0, p - q), (0, p - 2q), ... The last point is (0, r0), and r0 ≡ p (mod q).

    • x + y = p - q, p - 2q, ..., r0. We can write p = kq + r0.

    Result 1: If function returns TRUE, z is in {p - q, p - 2q, ..., r0}.

    • z ≡ r0 (mod q)

    Then the RED route goes to B1, then BLUE route to C1.

    If we extend B1C1 to the back, we get A1 on the y-axis, and the x + y in A1/B1/C1 is SAME.

    • From A1, we get (0, p - q + r0), (0, p - 2q + r0), ... The last point is (0, r1)

    • x + y = p - q + r0, p - 2q + r0, ..., r1

    • Here, r1 ≡ (p + r0) (mod q) ≡ (p mod q) + (r0 mod q) ≡ 2r0 (mod q)

    Result 2: If function returns TRUE, z is in {p - q + r0, p - 2q + r0, ..., r1}.

    • z ≡ r1 (mod q) ≡ (2r0 mod q)

    ..........

    Result k: If function returns TRUE.

    • z ≡ r(k-1) (mod q) ≡ kr0 (mod q)

    Conclution

    If function returns TRUE. There MUST EXIST a k, that kr0 ≡ z (mod q).

    The problem becomes that whether the formula kr0 ≡ z (mod q) has a root k.

    • If r0 = 0, then z mod q MUST equals to 0.
    • If r0 ≠ 0, then:

    Some special cases

    1. z = 0 is always TRUE, because we ALWAYS start from (0, 0).

    2. z = x + y is always TRUE, because we ALWAYS end at (x, y).

    3. When x = 0 (or y = 0), we only need to judge z = y (or z = x).

    4. When x = y, since the light path diagram can ONLY go from (0, 0) to (0, y),and then to (x, 0) and (x, y), z MUST be 0, x, 2x.


    Code

    class Solution {
    public:
        int gcd(int a, int b)
        {
            if(a % b == 0)
            {
                return b;
            }else{
                return gcd(b, a % b);
            }
        }
        bool canMeasureWater(int x, int y, int z) {
            if(z == 0 || z == x + y) return true;
            if(z > x + y) return false;
            if(x == 0) return z == y;
            if(y == 0) return z == x;
            if(x == y) return z == x;
            int y_in = (y > x)? y : x;
            int x_in = (y > x)? x : y;
            int r = y_in % x_in;
            if (r == 0)
            {
                return z % x_in == 0;
            }else{
                return z % gcd(r, x_in) == 0;
            }
        }
    };
    


  • 0

    Fails for example x=0, y=2, z=1.


  • 0

    Thanks, I have added this test case.


  • 0
    C

    Testcase 34,5,6, need to return true,while it is not.


  • 0
    K

    It returns true. I have just tested.


  • 0
    Z

    """
    class Solution(object):
    def gcd(self, a, b):
    if a % b == 0:
    return b
    else:
    return self.gcd(b, a%b)

    def canMeasureWater(self, x, y, z):
       
        if z==0 or z == x+y:
            return True
        if z > x + y :
            return False
        if x == 0:
            return z == y
        if y == 0:
            return z == x
        if x == y:
            return z == x
            
        y_in = y if y > x else x
        x_in = x if y > x else y
        
        r = y_in % x_in 
        
        if r == 0:
            return z % x_in == 0
        else:
            return z % self.gcd(r, x_in) == 0
    

    """


Log in to reply
 

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