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 1: (From the famous “Die Hard” example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
Solution:
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if(x+y<z) return false;
if(x==0 || y==0) return x==z || y==z;
return z%gcd(x,y)==0;
}
public int gcd(int x, int y){
return y==0 ? x : gcd(y, x%y);
}
}
Discussion
You are at the side of a river. 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. Determine the minimum no of operations to be performed to obtain d litres of water in one of jug. The operations you can perform are:
Empty a Jug Fill a Jug Pour water from one jug to the other until one of the jugs is either empty or full. There are several ways of solving this problem including BFS and DP. In this article an arithmetic approach to solve the problem is discussed. 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. For example, if we have a jug J1 of 5 litre (n = 5) and another jug J2 of 3 litre (m = 3) and we have to measure 1 litre of water using them. The associated equation will be 5n + 3m = 1. First of all this problem can be solved since gcd(3,5) = 1 which divides 1 (See this for detailed explanation). Using the Extended Euclid algorithm, we get values of n and m for which the equation is satisfied which are n = 2 and m = -3. These values of n, m also have some meaning like here n = 2 and m = -3 means that we have to fill J1 twice and empty J2 thrice. Now to find the minimum no of operations to be performed we have to decide which jug should be filled first. Depending upon which jug is chosen to be filled and which to be emptied we have two different solutions and the minimum among them would be our answer.
Solution 1 (Always pour from m litre jug into n litre jug)
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.
Repeat steps 1,2,3 till either n litre jug or the m litre jug contains d litres of water. Each of steps 1, 2 and 3 are counted as one operation that we perform. Let us say algorithm 1 achieves the task in C1 no of operations.
Solution 2 (Always pour from n litre jug into m litre jug)
1.Fill the n litre jug and empty it into m litre jug.
2.Whenever the n litre jug becomes empty fill it.
3.Whenever the m litre jug becomes full empty it.
Repeat steps 1, 2 and 3 till either n litre jug or the m litre jug contains d litres of water. Let us say solution 2 achieves the task in C2 no of operations.
Now our final solution will be minimum of C1 and C2.
// C++ program to count minimum number of steps
// required to measure d litres water using jugs
// of m litres and n litres capacity.
#include <bits/stdc++.h>
using namespace std;
// Utility function to return GCD of 'a'
// and 'b'.
int gcd(int a, int b)
{
if (b==0)
return a;
return gcd(b, a%b);
}
/* fromCap -- Capacity of jug from which
water is poured
toCap -- Capacity of jug to which
water is poured
d -- Amount to be measured */
int pour(int fromCap, int toCap, int d)
{
// Initialize current amount of water
// in source and destination jugs
int from = fromCap;
int to = 0;
// Initialize count of steps required
int step = 1; // Needed to fill "from" Jug
// Break the loop when either of the two
// jugs has d litre water
while (from != d && to != d)
{
// Find the maximum amount that can be
// poured
int temp = min(from, toCap - to);
// Pour "temp" litres from "from" to "to"
to += temp;
from -= temp;
// Increment count of steps
step++;
if (from == d || to == d)
break;
// If first jug becomes empty, fill it
if (from == 0)
{
from = fromCap;
step++;
}
// If second jug becomes full, empty it
if (to == toCap)
{
to = 0;
step++;
}
}
return step;
}
// Returns count of minimum steps needed to
// measure d litre
int minSteps(int m, int n, int d)
{
// To make sure that m is smaller than n
if (m > n)
swap(m, n);
// For d > n we cant measure the water
// using the jugs
if (d > n)
return -1;
// If gcd of n and m does not divide d
// then solution is not possible
if ((d % gcd(n,m)) != 0)
return -1;
// Return minimum two cases:
// a) Water of n litre jug is poured into
// m litre jug
// b) Vice versa of "a"
return min(pour(n,m,d), // n to m
pour(m,n,d)); // m to n
}
// Driver code to test above
int main()
{
int n = 3, m = 5, d = 4;
printf("Minimum number of steps required is %d",
minSteps(m, n, d));
return 0;
}