Pasos mínimos para cambiar N a 1 cambiándolo a 2*N o N/10 en cualquier paso

Dado un número entero N, encuentre el número mínimo de operaciones para cambiar N a 1. Si no es posible, imprima -1. Una operación se define como convertir N al número 2*N o convertir N al número N/10 (solo si N es divisible por 10).

Ejemplos:

Entrada: N = 50
Salida: 3
Explicación: N se puede convertir a 1 en 3 pasos de la siguiente manera:
-> Primero, multiplique N por 2 y cambie N de 50 a 100 (2*N)
-> Luego, divida N por 10 y cambia N de 100 a 10 (N/10)
-> Y luego, divide N por 10 y cambia N de 10 a 1 (N/10)

Entrada: N = 120
Salida: -1
Explicación: No hay forma posible de que Geek llegue a la posición 1.

Enfoque: N puede convertirse en 1 solo si N es reducible a 1 ya sea multiplicando por 2 o dividiendo por 10 en cada paso. Ahora N no se puede reducir a 1 siguiendo estos pasos si N tiene un factor primo distinto de 2 y 5 . Además, si el número de 2 es mayor que 5 en la factorización prima de N , N no puede reducirlo a 1 porque no será posible neutralizar todos los 2 .. Los números iguales de 2 y 5 se pueden neutralizar dividiendo el número por 10 . Los 5 adicionales se pueden neutralizar multiplicando con 2 adicionales y luego dividiendo por 10 . Siga los pasos a continuación para resolver el problema:

• Inicialice las variables dos y cinco como 0 para contar el número 2 y el número 5 en la factorización prima del número N.
• Iterar en un ciclo while hasta que N%2 sea igual a 0 y realizar los siguientes pasos:
  • Divide el número N por 2.
  • Aumenta el valor de dos en 1.
• Iterar en un ciclo while hasta que N%5 sea igual a 0 y realizar los siguientes pasos:
  • Divide el número N entre 5.
  • Aumenta el valor de cincos en 1.
• Si N es igual a 1 y el número de dos es menor que el número de cinco, entonces, escriba 2*cinco-dos como respuesta.
• De lo contrario, imprime -1.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if N can be changed
// to 1 or not.
void check(int N)
{
    int twos = 0, fives = 0;
 
    // Count the number of 2 in the prime
    // factorisation of N
    while (N % 2 == 0) {
        N /= 2;
        twos++;
    }
 
    // Count the number of 5 in the prime
    // factorisation of N
    while (N % 5 == 0) {
        N /= 5;
        fives++;
    }
 
    if (N == 1 && twos <= fives) {
        cout << 2 * fives - twos;
    }
    else {
        cout << -1;
    }
}
 
// Driver Code
int main()
{
    int N = 50;
 
    check(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to check if N can be changed
// to 1 or not.
static void check(int N)
{
    int twos = 0, fives = 0;
 
    // Count the number of 2 in the prime
    // factorisation of N
    while (N % 2 == 0)
    {
        N /= 2;
        twos++;
    }
 
    // Count the number of 5 in the prime
    // factorisation of N
    while (N % 5 == 0)
    {
        N /= 5;
        fives++;
    }
 
    if (N == 1 && twos <= fives)
    {
        System.out.println( 2 * fives - twos);
    }
    else
    {
        System.out.println(-1);
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 50;
     
    check(N);
}
}
 
// This code is contributed by Potta Lokesh

# Python 3 program for the above approach
 
# Function to check if N can be changed
# to 1 or not.
def check(N):
    twos = 0
    fives = 0
 
    # Count the number of 2 in the prime
    # factorisation of N
    while (N % 2 == 0):
        N /= 2
        twos += 1
 
    # Count the number of 5 in the prime
    # factorisation of N
    while (N % 5 == 0):
        N /= 5
        fives += 1
 
    if (N == 1 and twos <= fives):
        print(2 * fives - twos)
 
    else:
        print(-1)
 
# Driver Code
if __name__ == '__main__':
    N = 50
    check(N)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if N can be changed
// to 1 or not.
static void check(int N)
{
    int twos = 0, fives = 0;
 
    // Count the number of 2 in the prime
    // factorisation of N
    while (N % 2 == 0) {
        N /= 2;
        twos++;
    }
 
    // Count the number of 5 in the prime
    // factorisation of N
    while (N % 5 == 0) {
        N /= 5;
        fives++;
    }
 
    if (N == 1 && twos <= fives) {
        Console.Write( 2 * fives - twos);
    }
    else {
        Console.Write(-1);
    }
}
 
// Driver Code
public static void Main()
{
     int N = 50;
 
    check(N);
}
}
 
// This code is contributed by sanjoy_62.

<script>
 
// JavaScript program for the above approach
 
// Function to check if N can be changed
// to 1 or not.
function check(N)
{
    var twos = 0, fives = 0;
     
    // Count the number of 2 in the prime
    // factorisation of N
    while (N % 2 == 0)
    {
        N /= 2;
        twos++;
    }
 
    // Count the number of 5 in the prime
    // factorisation of N
    while (N % 5 == 0)
    {
        N /= 5;
        fives++;
    }
 
    if (N == 1 && twos <= fives)
    {
        document.write(2 * fives - twos);
    }
    else
    {
        document.write(-1);
    }
}
 
// Driver Code
var N = 50;
check(N);
 
// This code is contributed by shivanisinghss2110
 
</script>

3

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)