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

• 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

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

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;
}
}
};
``````

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

• Thanks, I have added this test case.

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

• It returns true. I have just tested.

• """
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
``````

"""

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