2
$\begingroup$

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-

  1. Fill the m litre jug and empty it into n litre jug.
  2. Whenever the m litre jug becomes empty fill it.
  3. Whenever the n litre jug becomes full empty it.
  4. 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?

$\endgroup$
2
$\begingroup$

The numbers $x$ and $y$ will turn up in the algorithm as the number of times you fill and empty the two jugs. You don't need to know them if you can tell when you have $d$ liters of water in one of the jugs.

But if you can't tell when you have $d$ liters (since the jugs have no markings), you'll need to count the fillings and emptyings. You'll fill the size $m$ container $x$ times. You'll empty the size $n$ container $-y$ times ($y$ will be negative, so $-y$ is positive and suitable for counting). Once you've done the respective operations the right number of times, you'll have $d$ liters of water left.

$\endgroup$
  • $\begingroup$ Oh right..!! Is there any way I can count number of operations needed directly from the values of x and y, since I know how many times I have to fill and empty a jug? $\endgroup$ – shiwang Jun 15 '18 at 17:56
  • $\begingroup$ And what is the intuition behind these 4 steps? $\endgroup$ – shiwang Jun 15 '18 at 17:59
  • 1
    $\begingroup$ I'm not sure what you mean by "operations"? If you want to count the number of fill and empty operations, you'll get $x - y$, but if you want to count the pours between too, you'd need to add some extra amount. Maybe double, since each fill of $m$ includes a pour, and each empty of $n$ interrupts a pour and splits it into two? As for the intuition, the algorithm keeps an amount of water equal to $m k \mod n$ as $k$ increases from zero to $x$. At the end, you have $m x \mod n$ water, which is equal to $d$. $\endgroup$ – Blckknght Jun 15 '18 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.