Water Jug Problem in Java

Water Jug Problem is one of the most important problems to solve in Java. The water jug problem is a problem where we have two jugs, “i” liter jug and “j” liter jug (0 < i < j). Both jugs will initially be empty, and they don’t have marking to measure small quantities. Now, we need to measure d liters of water by using these two jugs where d < j. We use the following three operations to measure small quantities by using the two jars:

Empty a Jug.
Fill a Jug
We pour the water of one jug into another one until one of them is either full or empty.

In Java, we implement the logic for getting the minimum number of operations required to measure the d liter quantity of water.

There are various ways to solve water jug problems in Java, including GCD, BFS, and DP. In this section, we implement the logic for solving the Water Jug problem by using GCD.

WaterJugProblemExample.java

  // import required classes and packages if any  import java.io.*;  import java.util.Scanner;  // create class WaterJugProblemExample to solve water jug problem in Java  class WaterJugProblemExample {    //create function getGCD() that returns GCD of ‘x’ and ‘y’.  public static int getGCD(int x, int y) {  if (y == 0) {  return x;  }    return getGCD(y, x % y);  }    /* create method pourWater() that accept three parameters, i.e., fromCapacity, toCapacity and d*/  /*fromCapacity is the capacity of the jug from which water is poured, toCapacity is the capacity of the jug to which water is poured, and ltr is the amount of water to be measured */  public static int pourWater(int fromCapacity, int toCapacity, int d) {    // declare and initialize variables which indicate the current amount of water in source and destination jugs  int fromCap = fromCapacity;  int toCap = 0;    // declare and initialize variable ‘reqStep’ that will help us to fill from jug  int reqStep = 1;    // use while loop to fill d ltr amount and break it when one of the two jugs has d liter amount  while (fromCap != d && toCap != d) {    // find maximum amount of water which we can pour  int maxPaur = Math.min(fromCap, toCapacity – toCap);    // we pour “maxPaur” liters water from “fromCap” to “toCap”  toCap = toCap + maxPaur;  fromCap = fromCap – maxPaur;    // increment the value of reqStep  reqStep++;    // check whether “fromCap” or “toCap” has d liters of water  if (fromCap == d || toCap == d)  break;    // We fill the first jug when it becomes empty  if (fromCap == 0) {  fromCap = fromCapacity;  reqStep++;  }    // we empty the second jug when it becomes full  if (toCap == toCapacity) {  toCap = 0;  reqStep++;  }  }  // return total number of required steps  return reqStep;  }    // create findMisSteps() method that will returns minimum steps needed for messuring d liter  public static int findMinSteps(int i, int j, int d) {    if (i > j) {  int temp = i;  i = j;  j = i;  }    // we can’t messure the water using the jugs if d > n  if (d > j) {  return -1;// we return -1 in this case  }  // We cannot solve the water jug problem when gcd of j and i is not possible to divide by d  if ((d % getGCD(j, i)) != 0)  return -1;// we return -1 in this case    // if the above two conditions are not matched, it return following two cases:  // x) Water of j liter jug is poured into i liter jug  // y) Vice versa of “x”  return Math.min(pourWater(j, i, d), // j to i  pourWater(i, j, d)); // i to j  }    // main() method  public static void main(String[] args) {    // initialize variables for the size of jugs and amount of water which we want to measure  int i, j, d;    // create Scanner class object to take input from user  Scanner sc = new Scanner(System.in);    System.out.println(“Enter the size of Jug1 in liters”);  i = sc.nextInt();    System.out.println(“Enter the size of Jug2 in liters”);  j = sc.nextInt();    System.out.println(“Enter the amount of water which you want to messure:”);  d = sc.nextInt();    // close Scanner class object  sc.close();    System.out.println(“Minimum number of steps required to messure water is ” + findMinSteps(i, j, d));  }  }  

Output:

We can use one more approach for solving Water Jug problem whose code implementation is given below:

WaterJugProblemExample1.java

  // import required classes and packages if any  import java.util.*;  // create class WaterJugProblemExample1 to solve Water Jug problem  class WaterJugProblemExample1{  // main() method start      public static void main(String sap[]){      // create Scanner class object to take input from user      Scanner scan = new Scanner(System.in);        // tank1 is the capacity of the small tank      System.out.print(“Enter value for Tank1, i.e., odd capacity of small tank: “);      int tank1 = scan.nextInt();        // tank2 is the capacity of the large tank      System.out.print(“nEnter value for Tank2, i.e., odd capacity of large tank: “);      int tank2 = scan.nextInt();            scan.close();        // initialize variable count that defines number of iterations      int count = tank1 + tank2;        /* jug1 and jug2 are the arrays that would hold the values for smaller larger tank */      int jug1[] = new int[count];      int jug2[] = new int[count];        int j = 0;        // initialize jug1[0] and jug2[0] with tank1 and 0 respectively      jug1[j] = tank1;      jug2[j] = 0;      j++;        // initialize jug1[1] and jug2[1] with 0 and tank1      jug1[j] = 0;      jug2[j] = tank1;      j++;        while(j < count){            if(jug1[ j – 1 ] > 0){                 // jug1 is not empty when it has any amount of water                 jug1[j] = jug1[ j – 1 ];                 jug2[j] = 0;            } else{                 // when jug1 is empty                 jug1[j] = tank1;                 jug2[j] = jug2[ j – 1 ];            }            j++;              if(jug2[ j – 1 ] > 0){                 // jug2 is not empty when it has any amount of water                 if(jug1[ j – 1 ] + jug2[ j – 1 ] < tank2){                       // final result                       jug2[j] = jug1[ j – 1 ] + jug2[ j – 1 ];                       jug1[j] = 0;                 } else{                 int temp = jug2[ j – 1 ];                 temp = tank2 – temp;                 jug2[j] = temp + jug2[ j – 1 ];                    jug1[j] = jug1[ j – 1 ] – temp;                 }            }            else{                 // when jug2 is empty                 jug2[j] = jug1[ j – 1 ];                 jug1[j] = 0;            }           j++;      }      // show final result      for(j = 0; j;>

Output:

Next TopicElectricity Bill Program in Java

Water Jug Problem in Java

Water Jug Problem in Java

Use of final Keyword in Java

Custom Tags in JSP

You may also like