**Question:**

Given two vessels, one of which can accommodate ** a liters** of water and the other which can accommodate

**of water, determine the number of steps required to obtain exactly**

*b*liters**. You have infinite supply of water.**

*c*liters of water in one of the vesselsAt 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; }