Two Water Jug problem [MEDIUM]

Company: MAQ-Software, MakeMyTrip

Question:

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:

1. Empty a Jug
2. Fill a Jug
3. Pour water from one jug to the other until one of the jugs is either empty or full.

Input:
First line consists of T test cases. Only line of every test case consists of 3 spaced integers denoting m , n, and d respectively. 

Output:
Single line output, print the minimum number of operations.

Constraints:
1<=T<=100
1<=N,D<=100
1<=M<=N

Example:
Input:
2
8 56 46
3 5 4
Output:
-1
6

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int test_cases= sc.nextInt();

for(int t=0;t<test_cases;t++){

   int m=sc.nextInt();

   int n=sc.nextInt();

   int d=sc.nextInt();

   System.out.println(minsteps(m,n,d));

}

}

public static int minsteps(int m,int n,int d  ){

 

   if(d>n){

       return -1;

   }

   if ((d % gcd(n,m)) != 0)

        {return -1;}

   return Math.min(pour(m,n,d),pour(n,m,d));

}

public static int pour(int fromCap, int toCap, int d){

   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 = Math.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;

}

public static int gcd(int a,int b){

   if(b==0){

       return a;

   }

   return gcd(b,a%b);

}

}

Execution Time: 0.08 secs