# Water Jug Problem

Question:

Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the  number of steps required to obtain exactly c liters of water in one of the vessels. You have infinite supply of water.

At the beginning both vessels are empty. The following operations are counted as ‘steps’:

• emptying a vessel,
• filling a vessel,
• pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

Lets try solving it

Before calculating  steps, lets check what can we say if its possible or not given the values of a, b and c.
Its not possible if c > a and c > b, because then we are not having a vessel capable of holding c liters of water.
Its also not possible when c is not a multiple of hcf of a and b, because in that case we wont be able to make c liters ever.

Once its clear if its possible or not calculating minimum number of steps is easy.
If its possible then there are always 2 ways to do it, may be with different number of steps. What we do is, we recursively fill one bucket lets say a and empty it in b, and when b is full in between the process, we empty it, and again pour from a, and do this till the time we have c liters of water in either a or b, or both depending upon condition c < capacity of that vessel.
Second way would be to begin with b first. We will fill vessel b first , and start emptying it in a, and in case a is full in between we will empty a , and again pour water from b into a.

Example

Lets say we have 3 liters vessel A and 5 liters vessel B and we want to store 4 liters water C

Checking if its possible or not:
we can easily see 4 < 5 and also 4 is multiple of 1 (HCF of 5 and 3)

Lets try and fill 4 liters of water

```Way 1.
We will repeatedly fill A and pour it in B
A = 3 and B = 5
Vessel A            Vessel B         Steps
initially              0                  0               0
Fill A                 3                  0               1
Pour A in B            0                  3               2
Fill A again           3                  3               3
Pour A in B            1                  5               4
Empty B                1                  0               5
Pour A in B            0                  1               6
Fill A                 3                  1               7
Pour A in B            0                  4               8
So we have 4 liters in B by way 1 in 8 steps.

Way 2.
We will repeatedly fill B and pour it in A
A = 3 and B = 5
Vessel A            Vessel B         Steps
initially              0                  0               0
Fill B                 0                  5               1
Pour B in A            3                  2               2
Empty A                0                  2               3
Pour B in A            2                  0               4
Fill B                 2                  5               5
Pour B in A            3                  4               6
So we have 4 liters in B by way 2 in 6 steps.

```

Here’s the piece of C++ code for checking and calculating the number of steps required.

```
/*
checking if its possible to fill C liters of water
in either of two vessels of capacity a and b with
infinite supply of water.
*/
bool check(int a,int b,int c){
//boundary cases
if(c>a && c>b)){
return false;
}
//if c is multiple of HCF of a and b, then possible
if(c%gcd(a,b)==0){
return true;
}
//if c is not multiple of HCF of a and b, then not possible
return false;
}

/*
calculating steps
Method:  Start filling A and pouring it in B,
in case B is full in between empty it, and
again pour from A, and repeat the process.
*/
int steps(int A,int B,int C){
int steps = 0;
int capacityA = A;
int capacityB = B;
int temp;
//starting with empty buckets
A= 0;
B= 0;
//repeating till either one of A and B has C liters of water
while(A!=C && B!= C){
//if A is empty, Fill A by supply of water
if(A==0){
A = capacityA;
steps+=1;
}else if(B==capacityB){
//If B is full, in between the processempty it

B=0;
steps+=1;
}else{
/*
Else, pour from A to B
amount of water to be poured depends on how much B can hold
which would be volume left in B or capacity of A, whichever is less
*/
temp = min(capacityB-B,A);
B+=temp;
A-=temp;
steps+=1;
}

}
return  steps;
}

```