I was reading an article on Water Jug Problem. The problem is -You are given a m litre jug and a n litre jug where 0 < m < n. Both the jugs are initially empty. The jugs don’t have markings to allow measuring smaller quantities. You have to use the jugs to measure d litres of water where d < n.
I solved the problem using recursion that at every time I can do some possible number of operations, I try to perform all those operations and if I reach to some previous state, then I return from it. The time complexity of this solution is O(m*n).
Now, the method in the article says that the problem can be modeled by means of Diophantine equation of the form mx + ny = d which is solvable if and only if gcd(m, n) divides d. Also, the solution x,y for which equation is satisfied can be given using the Extended Euclid algorithm for GCD.
Then, we apply the following algorithm to find the solution-
- Fill the m litre jug and empty it into n litre jug.
- Whenever the m litre jug becomes empty fill it.
- Whenever the n litre jug becomes full empty it.
- Repeat steps 1,2,3 till either n litre jug or the m litre jug contains d litres of water.
So, What is the intuition behind these 4 steps, that when they are done in this order they will always give the right answer?
Moreover, we are not using x and y that we found using the extended euclidean, then why are we finding them?