*Apart from the GCD solution* many have discussed, can we solve this with some strategy?

I didn't know the math solution, and tried to see if I can find some patterns.

1 ) let's first have two jugs with **similar sizes**, say, 15 and 18. Of course we can measure the diff 3. Then our strategy is, try to repeatedly pour water from smaller jug into bigger jug until full. That is:

pour 15 units water into jug of size 18, pour again until full -> 12 left in the smaller jug

pour 12 units water into jug of size 18, pour again until full -> 9 left in the smaller jug

pour 9 units water into jug of size 18, pour again until full -> 6 left in the smaller jug

pour 6 units water into jug of size 18, pour again until full -> **3** left in the smaller jug

That **3** is what we need to stop - when we see a number the second time, we know we can't measure anything else.

So, we have:

```
15 18: 3 12 9 6 3
```

Can we observe this pattern with other jugs? We can:

```
15 17: 2 13 11 9 7 5 3 1 14 12 10 8 6 4 2
15 19: 4 11 7 3 14 10 6 2 13 9 5 1 12 8 4
```

2 ) When we have two jugs, **one big one small**, the strategy is a bit different. Say we have 4 and 14. Our strategy is, try to pour water repeatedly from bigger jug into smaller one:

pour 14 water from bigger jug into the smaller jug until full -> 10 left in the bigger jug

pour 10 water from bigger jug into the smaller jug until full -> 6 left in the bigger jug

pour 6 water from bigger jug into the smaller jug until full -> 2 left in the bigger jug (let's pour this 2 into the smaller one)

pour 14 water from bigger jug into the smaller jug until full -> 12 left in the bigger jug

pour 12 water from bigger jug into the smaller jug until full -> 8 left in the bigger jug

pour 8 water from bigger jug into the smaller jug until full -> **4** left in the bigger jug

This is the second time we see **4**, so we should stop. So we have:

```
4 14: 10 6 2 12 8 4
```

Similarly:

```
5 17: 12 7 2 14 9 4 16 11 6 1 13 8 3 15 10 5
5 16: 11 6 1 12 7 2 13 8 3 14 9 4 15 10 5
```

A java implementing here:

```
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {e
int l = Math.min(x,y), h = Math.max(x,y);
int d = h - l;
// some special cases
if (z == 0) return true;
if (z > x + y) return false; // big z
if (l == 0) return h == z;
if (d == 0) return z == x || z == x + y; // same jug
if (x == z || y == z || x + y == z) return true;
int cur;
if (d < l) { // similar jugs
if (d == z || d + x == z || d + y == z) return true;
cur = l - d;
while (cur != d) {
if (cur == z || cur + x == z || cur + y == z) return true;
if (cur < d) {
cur = l - (h - cur - l);
} else {
cur -= d;
}
}
} else { // one big one small
cur = h - l;
while (cur != l) {
if (cur == z || cur + l == z) return true;
if (cur < l) {
cur = h - (l - cur);
} else {
cur -= l;
}
}
}
return false;
}
}
```

It's kind of interesting, but I guess we are still better off with the short GCD solution in an interview - maybe Microsoft just wanted to ask how to find GCD :P