Given two positive integers A and B. The task is to minimize operations required to reduce A and B to 1. There are two types of operation:
- Decrement either A or B by 1.
- Divide A by B or B by A or perform both divisions simultaneously only if the remainder on division is 0.
Example:
Input: A = 13, B = 5
Output: 6
Explanation: Below are the operations performed to reduce A and B to 1.Initially A = 13, B = 5
Step 1: Decrement A by 1: A = 12, B = 5
Step 2: Decrement B by 1: A = 12, B = 4
Step 3: Divide A by B and assign it to A : A = 3, B = 4
Step 4: Decrement B by 1: A = 3 B = 3
Step 5: Divide both A by B and B by A, assign it to A and B respectively: A = 1, B = 1
Therefore, total 5 steps required to reduce A and B to 1. Which is minimum possible.Input: A = 3, B = 27
Output: 3
Approach: This problem can be solved by using recursion. Create a recursive and Take a variable say cntOperations = 0 to keep track of the number of operations performed. For base condition check if A=1 and B=1, then return cntOperations otherwise, check for each possible operation that can be performed.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Recursive function to find minimum operation// required to reduce A and B to 1int solve(int A, int B, int ans = 0){ // Base Condition: When A and B reduced to 1 if (A == 1 && B == 1) { return ans; } // If A and B are equal if (A % B == 0 && B % A == 0) { return solve(A / B, B / A, ans + 1); } // If A is divisible by B else if (A % B == 0 && B % A != 0) { return solve(A / B, B, ans + 1); } // If B is divisible by A else if (A % B != 0 && B % A == 0) { return solve(A, B / A, ans + 1); } // If A-1 is even else if ((A - 1) % 2 == 0) { return solve(A - 1, B, ans + 1); } // If B-1 is even else if ((B - 1) % 2 == 0) { return solve(A, B - 1, ans + 1); } else { // If A is less than B if (A < B) { return solve(A - 1, B, ans + 1); } // If B is less than A else { return solve(A, B - 1, ans + 1); } }}// Driver Codeint main(){ int A = 13; int B = 5; cout << solve(A, B);} |
Java
// Java program for above approachclass GFG{ // Recursive function to find minimum operation // required to reduce A and B to 1 public static int solve(int A, int B, int ans) { // Base Condition: When A and B reduced to 1 if (A == 1 && B == 1) { return ans; } // If A and B are equal if (A % B == 0 && B % A == 0) { return solve(A / B, B / A, ans + 1); } // If A is divisible by B else if (A % B == 0 && B % A != 0) { return solve(A / B, B, ans + 1); } // If B is divisible by A else if (A % B != 0 && B % A == 0) { return solve(A, B / A, ans + 1); } // If A-1 is even else if ((A - 1) % 2 == 0) { return solve(A - 1, B, ans + 1); } // If B-1 is even else if ((B - 1) % 2 == 0) { return solve(A, B - 1, ans + 1); } else { // If A is less than B if (A < B) { return solve(A - 1, B, ans + 1); } // If B is less than A else { return solve(A, B - 1, ans + 1); } } } // Driver Code public static void main(String args[]) { int A = 13; int B = 5; System.out.println(solve(A, B, 0)); }}// This code is contributed by gfgking, |
Python3
# python program for above approach# Recursive function to find minimum operation# required to reduce A and B to 1def solve(A, B, ans=0): # Base Condition: When A and B reduced to 1 if (A == 1 and B == 1): return ans # If A and B are equal if (A % B == 0 and B % A == 0): return solve(A // B, B // A, ans + 1) # If A is divisible by B elif (A % B == 0 and B % A != 0): return solve(A // B, B, ans + 1) # If B is divisible by A elif (A % B != 0 and B % A == 0): return solve(A, B // A, ans + 1) # If A-1 is even elif ((A - 1) % 2 == 0): return solve(A - 1, B, ans + 1) # If B-1 is even elif ((B - 1) % 2 == 0): return solve(A, B - 1, ans + 1) else: # If A is less than B if (A < B): return solve(A - 1, B, ans + 1) # If B is less than A else: return solve(A, B - 1, ans + 1)# Driver Codeif __name__ == "__main__": A = 13 B = 5 print(solve(A, B))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { // Recursive function to find minimum operation // required to reduce A and B to 1 static int solve(int A, int B, int ans) { // Base Condition: When A and B reduced to 1 if (A == 1 && B == 1) { return ans; } // If A and B are equal if (A % B == 0 && B % A == 0) { return solve(A / B, B / A, ans + 1); } // If A is divisible by B else if (A % B == 0 && B % A != 0) { return solve(A / B, B, ans + 1); } // If B is divisible by A else if (A % B != 0 && B % A == 0) { return solve(A, B / A, ans + 1); } // If A-1 is even else if ((A - 1) % 2 == 0) { return solve(A - 1, B, ans + 1); } // If B-1 is even else if ((B - 1) % 2 == 0) { return solve(A, B - 1, ans + 1); } else { // If A is less than B if (A < B) { return solve(A - 1, B, ans + 1); } // If B is less than A else { return solve(A, B - 1, ans + 1); } } } // Driver Code public static void Main(String[] args) { int A = 13; int B = 5; Console.WriteLine(solve(A, B, 0)); }}// This code is contributed by dwivediyash |
Javascript
<script> // JavaScript program for above approach // Recursive function to find minimum operation // required to reduce A and B to 1 const solve = (A, B, ans = 0) => { // Base Condition: When A and B reduced to 1 if (A == 1 && B == 1) { return ans; } // If A and B are equal if (A % B == 0 && B % A == 0) { return solve(parseInt(A / B), parseInt(B / A), ans + 1); } // If A is divisible by B else if (A % B == 0 && B % A != 0) { return solve(parseInt(A / B), B, ans + 1); } // If B is divisible by A else if (A % B != 0 && B % A == 0) { return solve(A, parseInt(B / A), ans + 1); } // If A-1 is even else if ((A - 1) % 2 == 0) { return solve(A - 1, B, ans + 1); } // If B-1 is even else if ((B - 1) % 2 == 0) { return solve(A, B - 1, ans + 1); } else { // If A is less than B if (A < B) { return solve(A - 1, B, ans + 1); } // If B is less than A else { return solve(A, B - 1, ans + 1); } } } // Driver Code let A = 13; let B = 5; document.write(solve(A, B)); // This code is contributed by rakeshsahni</script> |
Output
6
Time Complexity: O(max(A, B))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
