Number of continuous reductions of A from B or B from A to make them (1, 1)
Given two integers A and B, the task is to find the minimum number of operations required to change this pair to (1, 1). In each operation (A, B) can be changed to (A – B, B) where A > B.
Note: If there is no possible solution to reach (1, 1), print -1.
Examples:
Input: A = 7, B = 8
Output: 7
Explanation:
Operation 1: (A, B) => (7, 8) => (7, 1)
Operation 2: (A, B) => (7, 1) => (6, 1)
Operation 3: (A, B) => (6, 1) => (5, 1)
Operation 4: (A, B) => (5, 1) => (4, 1)
Operation 5: (A, B) => (4, 1) => (3, 1)
Operation 6: (A, B) => (3, 1) => (2, 1)
Operation 7: (A, B) => (2, 1) => (1, 1)Input: A = 75, B = 17
Output: 10
Naive Approach: The idea is to use recursion and update the pair as (A, A – B), where A > B, and increase the number of operations required by 1. If at any step, any element of the pair is less than 1 then it is not possible to reach (1, 1).
Below is the implementation of the above approach:
C++
// C++ implementation to find the // minimum number of operations // required to reach (1, 1) #include <bits/stdc++.h> using namespace std; // Function to find the minimum // number of steps required int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) return -1; // Condition to check if the // pair is reached to 1, 1 if (a == 1 && b == 1) return c; // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a - b, b, c + 1); } // Driver Code int main() { int a = 75; int b = 17; cout << minimumSteps(a, b, 0) << endl; } // This code is contributed by AbhiThakur |
Java
// Java implementation to find the // minimum number of operations // required to reach (1, 1) class GFG{ // Function to find the minimum // number of steps required static int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1 ) return - 1 ; // Condition to check if the // pair is reached to 1, 1 if (a == 1 && b == 1 ) return c; // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a - b, b, c + 1 ); } // Driver Code public static void main(String []args) { int a = 75 ; int b = 17 ; System.out.println(minimumSteps(a, b, 0 )); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the # minimum number of operations # required to reach (1, 1) # Function to find the minimum # number of steps required def minimumSteps(a, b, c): # Condition to check if it # is not possible to reach if a < 1 or b < 1 : return - 1 # Condition to check if the # pair is reached to 1, 1 if a = = 1 and b = = 1 : return c # Condition to change the # A as the maximum element if a < b: a, b = b, a return minimumSteps(a - b, b, c + 1 ) # Driver Code if __name__ = = "__main__" : a = 75 ; b = 17 print (minimumSteps(a, b, 0 )) |
C#
// C# implementation to find the // minimum number of operations // required to reach (1, 1) using System; class GFG{ // Function to find the minimum // number of steps required static int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) return -1; // Condition to check if the // pair is reached to 1, 1 if (a == 1 && b == 1) return c; // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a - b, b, c + 1); } // Driver Code public static void Main() { int a = 75; int b = 17; Console.WriteLine(minimumSteps(a, b, 0)); } } // This code is contributed by AbhiThakur |
Javascript
<script> // JavaScript implementation to find the // minimum number of operations // required to reach (1, 1) // Function to find the minimum // number of steps required function minimumSteps(a, b, c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) return -1; // Condition to check if the // pair is reached to 1, 1 if (a == 1 && b == 1) return c; // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a - b, b, c + 1); } // Driver Code let a = 75; let b = 17; document.write(minimumSteps(a, b, 0) + "<br>" ); // This code is contributed by Surbhi Tyagi. </script> |
10
Efficient Approach: The idea is to use the Euclidean algorithm to solve this problem. By this approach, we can go from (A, B) to (A % B, B) in the A/B steps. But if the minimum of the A and B is 1, then we can reach (1, 1) in A – 1 steps.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // minimum number of operations // required to reach (1, 1) #include <bits/stdc++.h> using namespace std; // Function to find the minimum int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) { return -1; } // Condition to check if the // pair is reached to 1, 1 if (min(a, b) == 1) { return c + max(a, b) - 1; } // Condition to change the // A as the maximum element if (a < b) { swap(a, b); } return minimumSteps(a % b, b, c + (a / b)); } // Driver Code int main() { int a = 75, b = 17; cout << minimumSteps(a, b, 0) << endl; return 0; } // This code is contributed by rutvik_56 |
Java
// Java implementation to find the // minimum number of operations // required to reach (1, 1) import java.util.*; class GFG{ // Function to find the minimum static int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1 ) { return - 1 ; } // Condition to check if the // pair is reached to 1, 1 if (Math.min(a, b) == 1 ) { return c + Math.max(a, b) - 1 ; } // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a % b, b, c + (a / b)); } // Driver Code public static void main(String[] args) { int a = 75 , b = 17 ; System.out.print( minimumSteps(a, b, 0 ) + "\n" ); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to find the # minimum number of operations # required to reach (1, 1) # Function to find the minimum # number of steps required def minimumSteps(a, b, c): # Condition to check if it # is not possible to reach if a < 1 or b < 1 : return - 1 # Condition to check if the # pair is reached to 1, 1 if min (a, b) = = 1 : return c + max (a, b) - 1 # Condition to change the # A as the maximum element if a < b: a, b = b, a return minimumSteps(a % b, b, c + a / / b) # Driver Code if __name__ = = "__main__" : a = 75 ; b = 17 print (minimumSteps(a, b, 0 )) |
C#
// C# implementation to find the // minimum number of operations // required to reach (1, 1) using System; class GFG{ // Function to find the minimum static int minimumSteps( int a, int b, int c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) { return -1; } // Condition to check if the // pair is reached to 1, 1 if (Math.Min(a, b) == 1) { return c + Math.Max(a, b) - 1; } // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a % b, b, c + (a / b)); } // Driver Code public static void Main() { int a = 75, b = 17; Console.Write(minimumSteps(a, b, 0) + "\n" ); } } // This code is contributed by Nidhi_biet |
Javascript
<script> // JavaScript implementation to find the // minimum number of operations // required to reach (1, 1) // Function to find the minimum function minimumSteps(a, b, c) { // Condition to check if it // is not possible to reach if (a < 1 || b < 1) { return -1; } // Condition to check if the // pair is reached to 1, 1 if (Math.min(a, b) == 1) { return c + Math.max(a, b) - 1; } // Condition to change the // A as the maximum element if (a < b) { a = a + b; b = a - b; a = a - b; } return minimumSteps(a % b, b, c + parseInt(a / b)); } // Driver Code var a = 75, b = 17; document.write(minimumSteps(a, b, 0) + "<br>" ); </script> |
10