Horje
Minimize operations to reduce A and B to 1 by decrementing 1 or dividing A by B and B by A

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:

  1. Decrement either A or B by 1.
  2. 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 1
int 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 Code
int main()
{
    int A = 13;
    int B = 5;
 
    cout << solve(A, B);
}

Java

// Java program for above approach
class 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 1
def 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 Code
if __name__ == "__main__":
 
    A = 13
    B = 5
 
    print(solve(A, B))
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using 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)


 


Reffered: https://www.geeksforgeeks.org

Game Theory

Related
Minimum cost to reduce A and B to 0 using square root or divide by 2 Minimum cost to reduce A and B to 0 using square root or divide by 2
Find the player who will win by choosing a number in range [1, K] with sum total N Find the player who will win by choosing a number in range [1, K] with sum total N
Check if all 3 Candy bags can be emptied by removing 2 candies from any one bag and 1 from the other two repeatedly Check if all 3 Candy bags can be emptied by removing 2 candies from any one bag and 1 from the other two repeatedly
Maximum number of bomb blasts that may occur before the thief gets caught Maximum number of bomb blasts that may occur before the thief gets caught
Find winner in game of N balls, in which a player can remove any balls in range [A, B] in a single move Find winner in game of N balls, in which a player can remove any balls in range [A, B] in a single move

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje