Water 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.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
- 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
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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in…math.stackexchange.com