Water Jug Problem

problem statement

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.

Solution : This is a well known problem. I knew how to solve it using heuristics but I also knew this is a mathematical problem.

It turns out this is a genuine mathematical problem. You need to know the maths behind it to successfully solve the problem because the heurestic technique is not determistic

So the principle behind this is lets say we have jugs x and y . Now According to Extended Euclidean theorem if

gcd(x, y) = a

then we can write a as

mx + ny = a

now if z % a == 0 then z = ka

mx + ny = ka or m (x/k) + n(y/k) = 1

here x/k and y/k are integers

now m and n according to extended euclidean theorem are integers

lets suppose than when m or n is positive it means adding water to the jug

and when m or n is negative it means removing or emptying the jug

so our requrement is

mx + ny = z

we have already found tha

m(x/k) + n(y/k) = 1

mutliplying both side by z

we have

mz(x/k) + n(y/k)*z = z

which means that we can measure water upto z litres using jugs of size(x/k) and (y/k)

so we will return true if z%(gcd(x, y)) == 0 of course when gcd(x,y) ==0 we would have to consider certain cases

As a cororolly to the problem we can establish that given x and y such that

gcd(x,y) ==1 or x and y are coprime .In such a configuration we can measure upto any capacity that is any z greater than 0 and less than or equal to x +y.

Links :