Water and Jug Problem

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.

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.

Example:

Input: x = 4, y = 9, z = 6
Output: True

Approach: Except few boundary conditions, if z is divisible by GCD of x and y then we will return true otherwise false. Let's see how we can prove it:

According to Extended Euclidean theorem, if gcd(x, y) = a then we can write it as 

mx + ny = a

if z % a == 0 then z = ka where k is some integer.

 mx + ny = ka

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

According to Extended Euclidean algorithm, m and y are integers. x/k and y/k are also integers.

Our requirement is:

mx + ny = z,

We have already proved that 

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

mz(x/k) + nz(y/k) = 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)) is 0.

Implementation in C#:

        public static bool CanMeasureWater(int x, int y, int z)

        {

            if (z == 0)

            {

                return true;

            }

            if (z > x + y)

            {

                return false;

            }

            int gcd = GCD(x, y);

            return z % gcd == 0;

        }

Complexity: O(logn)