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: 

Source:leetcode Water and Jug Problem

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