# C++ solution using Euclidean Algorithm

• ``````class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(z > x && z > y) return false;
return z%gcd(x, y) == 0;
}
private:
int gcd(int a, int b){
return b == 0?a:gcd(b, a%b);
}
};``````

• If (1,2,3) ,where z > max(x,y) is judged as false, there must be no other containers.

Then, how do you measure (4,3,2) ?

• 2 = 2 * 3 - 4

put C3 full;
dump C3 into C4;
put C3 full;
dump 1 from C3 into C4;
the remaining in C3 is 2;

• why (1,2,3) should be judged as false?

• I can see necessity, but I don't find sufficiency obvious at all. Please provide at least some explanation for that.

• I think you mean this.

``````class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
return z == 0 || (z <= x + y && z % gcd(x, y) == 0);
}
private:
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};``````

• still a little bug exist, take care of overflow when add x and y. z <= (long long)x + y

• used to be judged as false.

• Oh, yes, you are right.
We can always find a "action sequence" if Mx - Ny = gcd(x,y), and so is the multiple of gcd(x,y).
Thanks.

• Yup, thanks for pointing out :)

• Is this a ac solution?

``````if(z > x && z > y) return false;
``````

I think z can be greater than both x and y.

• @Ren.W Well, in the practice, z >x and z>y should be correct. For example, z = 3 and a = 1 and b = 2. But in this question, due to some unknown reasons, that case is false always.

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