Minimice las operaciones para reducir A o B a 0 reduciendo A de B o B de A

Dados dos números A y B , la tarea es encontrar el número mínimo de operaciones requeridas para reducir A o B a 0, donde cada operación A puede reducirse por B si A es mayor que igual a B, o viceversa.

Ejemplos:

Entrada: A = 5, B = 4
Salida: 5
Explicación:
Reducir B de A: A=1, B=4
Reducir A de B: A=1, B=3
Reducir A de B: A=1, B=2
Reducir A de B: A=1, B=1
Reducir B de A: A=0, B=1

Entrada: A=1, B=1
Salida: 1
Explicación:
Reducir A de B: A=0, B=0

Enfoque: El enfoque para resolver este problema es simplemente buscar números más grandes y reducir el número pequeño.

• Repita las siguientes operaciones hasta que al menos uno de los dos números se convierta en 0
  • Si A es mayor que igual a B, reduce B de A
  • Si A es más pequeño que A, reduce A de B
  • Para cada iteración de ciclo, almacene el conteo.
• Devuelve el recuento de iteraciones de bucle al final.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find Minimum number
// Of operations required to reduce
// Either A or B to Zero
 
#include <iostream>
using namespace std;
 
int countOperations(int num1, int num2)
{
    int cnt = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2)
            num1 -= num2;
        else
            num2 -= num1;
        cnt++;
    }
    return cnt;
}
 
// Driver Code
int main()
{
 
    int A = 5, B = 4;
    cout << countOperations(A, B);
    return 0;
}

// Java program to find Minimum number
import java.io.*;
 
class GFG {
 
  // Of operations required to reduce
  // Either A or B to Zero
 
  static int countOperations(int num1, int num2)
  {
    int cnt = 0;
    while (num1 > 0 && num2 > 0) {
      if (num1 >= num2)
        num1 -= num2;
      else
        num2 -= num1;
      cnt++;
    }
    return cnt;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int A = 5, B = 4;
    System.out.println(countOperations(A, B));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code for the above approach
def countOperations(num1, num2):
    cnt = 0
    while (num1 > 0 and num2 > 0):
        if (num1 >= num2):
            num1 -= num2
        else:
            num2 -= num1
        cnt += 1
 
    return cnt
 
# Driver Code
A,B = 5,4
print(countOperations(A, B))
 
# This code is contributed by shinjanpatra

// C# program to find Minimum number
// Of operations required to reduce
// Either A or B to Zero
using System;
class GFG {
 
  static int countOperations(int num1, int num2)
  {
    int cnt = 0;
    while (num1 > 0 && num2 > 0) {
      if (num1 >= num2)
        num1 -= num2;
      else
        num2 -= num1;
      cnt++;
    }
    return cnt;
  }
 
  // Driver Code
  public static void Main()
  {
 
    int A = 5, B = 4;
    Console.Write(countOperations(A, B));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
       function countOperations(num1, num2) {
           let cnt = 0;
           while (num1 > 0 && num2 > 0) {
               if (num1 >= num2)
                   num1 -= num2;
               else
                   num2 -= num1;
               cnt++;
           }
           return cnt;
       }
 
       // Driver Code
       let A = 5, B = 4;
       document.write(countOperations(A, B));
 
      // This code is contributed by Potta Lokesh
   </script>

5

Complejidad de tiempo: 0(MAX(A, B)), donde A y B son los dos números dados.
Espacio Auxiliar: 0(1)