Minimize divisions by 2 , 3 , or 5 required to make two given integers equal | Java program for the above approach ; Function to calculate GCD of two numbers ; Base Case ; Calculate GCD recursively ; Function to count the minimum number of divisions required to make X and Y equal ; Calculate GCD of X and Y ; Divide X and Y by their GCD ; Stores the number of divisions ; Iterate until X != Y ; Maintain the order X <= Y ; If X is divisible by 2 , then divide X by 2 ; If X is divisible by 3 , then divide X by 3 ; If X is divisible by 5 , then divide X by 5 ; If X is not divisible by 2 , 3 , or 5 , then print - 1 ; Increment count by 1 ; Print the value of count as the minimum number of operations ; Driver Code
import java . util . * ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ) ; } static void minimumOperations ( int X , int Y ) { int GCD = gcd ( X , Y ) ; X = X / GCD ; Y = Y / GCD ; int count = 0 ; while ( X != Y ) { if ( Y > X ) { int t = X ; X = Y ; Y = t ; } if ( X % 2 == 0 ) { X = X / 2 ; } else if ( X % 3 == 0 ) { X = X / 3 ; } else if ( X % 5 == 0 ) { X = X / 5 ; } else { System . out . print ( " - 1" ) ; return ; } count += 1 ; } System . out . println ( count ) ; } static public void main ( String args [ ] ) { int X = 15 , Y = 20 ; minimumOperations ( X , Y ) ; } }