Reducir N a 1 en movimientos mínimos ya sea multiplicando por 2 o dividiendo por 6

Dado un número entero N , encuentre el número mínimo de operaciones para reducir N a 1 usando las siguientes dos operaciones:

• Multiplica N por 2
• Divide N por 6, si N es divisible por 6

Si N no se puede reducir a 1, imprima -1 .

Ejemplos:

Entrada: N = 54
Salida: 5
Explicación: Realice las siguientes operaciones :

• Divida N por 6 y obtenga n = 9
• Multiplique N por 2 y obtenga n = 18
• Divida N por 6 y obtenga n = 3
• Multiplique N por 2 y obtenga n = 6
• Divide N por 6 para obtener n = 1

Por lo tanto, es necesario realizar un mínimo de 5 operaciones para reducir 54 a 1

Entrada: N = 12
Salida: -1

Enfoque: La tarea se puede resolver utilizando las siguientes observaciones. 

• Si el número consta de primos distintos de 2 y 3 , la respuesta es -1 , ya que N no se puede reducir a 1 con las operaciones anteriores.
• De lo contrario, sea cuenta2 el número de dos en la factorización de n y cuenta3 sea el número de tres en la factorización de n .
  • Si cuenta2 > cuenta3 entonces la respuesta es -1 porque no podemos deshacernos de todos los dos.
  • De lo contrario, la respuesta es (cuenta3−cuenta2) + cuenta3 .

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 find the minimum number
// of moves to reduce N to 1
void minOperations(int N)
{
    int count2 = 0, count3 = 0;
 
    // Number of 2's in the
    // factorization of N
    while (N % 2 == 0) {
        N = N / 2;
        count2++;
    }
 
    // Number of 3's in the
    // factorization of n
    while (N % 3 == 0) {
        N = N / 3;
        count3++;
    }
 
    if (N == 1 && (count2 <= count3)) {
        cout << (2 * count3) - count2;
    }
 
    // If number of 2's are greater
    // than number of 3's or
    // prime factorization of N contains
    // primes other than 2 or 3
    else {
        cout << -1;
    }
}
 
// Driver Code
int main()
{
    int N = 54;
    minOperations(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum number
// of moves to reduce N to 1
static void minOperations(int N)
{
    int count2 = 0, count3 = 0;
 
    // Number of 2's in the
    // factorization of N
    while (N % 2 == 0) {
        N = N / 2;
        count2++;
    }
 
    // Number of 3's in the
    // factorization of n
    while (N % 3 == 0) {
        N = N / 3;
        count3++;
    }
 
    if (N == 1 && (count2 <= count3)) {
        System.out.print((2 * count3) - count2);
    }
 
    // If number of 2's are greater
    // than number of 3's or
    // prime factorization of N contains
    // primes other than 2 or 3
    else {
        System.out.print(-1);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 54;
    minOperations(N);
}
}
 
// This code is contributed by shikhasingrajput

# python program for the above approach
 
# Function to find the minimum number
# of moves to reduce N to 1
def minOperations(N):
 
    count2 = 0
    count3 = 0
 
    # Number of 2's in the
    # factorization of N
    while (N % 2 == 0):
        N = N // 2
        count2 += 1
 
        # Number of 3's in the
        # factorization of n
    while (N % 3 == 0):
        N = N // 3
        count3 += 1
 
    if (N == 1 and (count2 <= count3)):
        print((2 * count3) - count2)
 
        # If number of 2's are greater
        # than number of 3's or
        # prime factorization of N contains
        # primes other than 2 or 3
    else:
        print(-1)
 
# Driver Code
if __name__ == "__main__":
 
    N = 54
    minOperations(N)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the minimum number
    // of moves to reduce N to 1
    static void minOperations(int N)
    {
        int count2 = 0, count3 = 0;
 
        // Number of 2's in the
        // factorization of N
        while (N % 2 == 0) {
            N = N / 2;
            count2++;
        }
 
        // Number of 3's in the
        // factorization of n
        while (N % 3 == 0) {
            N = N / 3;
            count3++;
        }
 
        if (N == 1 && (count2 <= count3)) {
            Console.WriteLine((2 * count3) - count2);
        }
 
        // If number of 2's are greater
        // than number of 3's or
        // prime factorization of N contains
        // primes other than 2 or 3
        else {
            Console.WriteLine(-1);
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 54;
        minOperations(N);
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum number
// of moves to reduce N to 1
function minOperations(N)
{
    let count2 = 0, count3 = 0;
 
    // Number of 2's in the
    // factorization of N
    while (N % 2 == 0)
    {
        N = Math.floor(N / 2);
        count2++;
    }
 
    // Number of 3's in the
    // factorization of n
    while (N % 3 == 0)
    {
        N = Math.floor(N / 3);
        count3++;
    }
 
    if (N == 1 && (count2 <= count3))
    {
        document.write((2 * count3) - count2);
    }
 
    // If number of 2's are greater
    // than number of 3's or prime
    // factorization of N contains
    // primes other than 2 or 3
    else
    {
        document.write(-1);
    }
}
 
// Driver Code
let N = 54;
 
minOperations(N);
 
// This code is contributed by Potta Lokesh
 
</script>

5

Complejidad temporal: O(logN)
Espacio auxiliar: O(1)