Two water jug problem in C++

In this tutorial, we will learn how to solve the two water jug problem in C++.

PROBLEM STATEMENT:

You are given two unmarked jugs with capacities x and y liters. Determine the moves to obtain exactly n liters of water in any of the two jugs or both by the end.
Given that:
1. There is infinite supply of water.
2. Both the jugs are empty at the beginning.
Operations allowed:
1. Empty /fill a jug completely with water.
2. Pour water from one jug to another until one of the jugs is either empty or full.

SOLUTION:

We will first see the steps to solve the given problem.

1. If it is possible to fill n liters of water using the two jugs with x and y liters.
It is possible only if
1. n<x or n<y
2. n%gcd(x,y) is equal to zero.
2. Fill x completely.
3. Pour x in y.
4. Empty y if it is full.
5. Check if x is empty or not. If x is not empty, repeat step 3-5. If x is empty, repeat steps 2-5.
6. Stop the process when n litres of water is obtained in any of the two jugs or both.

Now, we will implement these steps using C++ code.

#include<bits/stdc++.h>
using namespace std;
int x;
int y;
void show(int a, int b);
int min(int w, int z)
{
if (w < z)
return w;
else
return z;
}
void show(int a, int b)
{
cout << setw(12) << a << setw(12) << b<<endl;
}
void s(int n)
{
int xq = 0, yq = 0;
int t;
cout << setw(15) <<"FIRST JUG"<< setw(15) <<"SECOND JUG"<<endl;
while (xq != n && yq!=n )
{
if (xq == 0)
{
xq = x;
show(xq, yq);
}
else if (yq == y)
{
yq = 0;
show(xq, yq);
}
else
{
t = min(y - yq, xq);
yq= yq + t;
xq = xq - t;
show(xq, yq);
}
}
}
int main()
{
int n;
cout << "Enter the liters of water required out of the two jugs: ";
cin >> n;
cout << "Enter the capacity of the first jug: ";
cin >> x;
cout << "Enter the capacity of the second jug: ";
cin >> y;
if(n<x || n<y)
{ if(n%(__gcd(x,y))==0)
s(n);
else
cout<<"This is not possible....\n";
}
else
cout<<"This is not possible....\n";
}

OUTPUT:

Enter the liters of water required out of the two jugs: 2

Enter the capacity of the first jug: 4

Enter the capacity of the second jug: 3

FIRST JUG          SECOND JUG
4                  0
1                  3
1                  0
0                  1
4                  1
2                  3

So, we have solved the two water jug problem in C++. I hope you enjoyed it.