# LeetCode – Water and Jug Problem

Tags:

leetcode Water and Jug Problem

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.

Operations allowed:

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

Example 1:

Example 2:

The first thought to solve this problem is using deep first search.  By Defining the following function:

`fill(x, x_water, y, y_water, z)`

We have the following options:

1. If a simple calculation of  the current value of water can get the target z, we are done.
2. Fill the water from x to y based on x_water, y and y_water.
3. Fill the water from y to x based on y_water, x and x_water.

We can use the idea of memorization to return immediately if one state has been reached and the result is False.

The above method can not pass when x, y are too large. It turned out that this problem is equal to the following problem:

`m * x + n * y = z`, with the constraint that m and n are integers.

It turns out that, only when` z % GCD(x,y) == 0,` the above equation has valid solutions.

Reference: http://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm