Dado un número entero N , la tarea es reducir N a 1 mediante un número mínimo de operaciones de multiplicación por 2 y división por 10 . Si no se puede obtener 1 , imprima «-1» .
Ejemplos:
Entrada: N = 5
Salida: 2
Explicación:
A continuación se muestran las operaciones realizadas:
1ª operación: Multiplica N por 2. Por lo tanto, N = 5 * 2 = 10.
2da operación: Divide N por 10. Por lo tanto, N = 10/10 = 1.
Por lo tanto, el número mínimo de operaciones requeridas es 2.Entrada: N = 4
Salida: -1
Enfoque: La idea es verificar los factores primos del número M dado . Si el número dado tiene factores primos distintos de 2 y 5 , entonces no es posible reducir el número dado a 1 mediante las operaciones dadas. Si la cuenta de 2 excede la de 5 en sus factores primos, entonces no es posible reducir N a 1 ya que no se pueden reducir todas las potencias de 2 .
Siga los pasos a continuación para resolver el problema:
- Cuente el número de 2 presentes en los factores primos de N y guárdelo en una variable, digamos cnt2 , y actualice N a N / 2 cnt2 .
- Cuente el número de 5 s presentes en los factores primos de N y guárdelo en una variable, digamos cnt5 , y actualice N a N / 5 cnt5 .
- Después de completar los pasos anteriores, si N es 1 y cnt2 ≤ cnt5 , entonces el número mínimo de pasos requeridos es 2 * cnt5 – cnt2 .
- De lo contrario, imprima «-1» ya que N no se puede reducir a 1 con las operaciones dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // operations required to reduce N to 1 int minimumMoves(int n) { // Stores count of powers of 2 and 5 int cnt2 = 0, cnt5 = 0; // Calculating the primefactors 2 while (n % 2 == 0) { n /= 2; cnt2++; } // Calculating the primefactors 5 while (n % 5 == 0) { n /= 5; cnt5++; } // If n is 1 and cnt2 <= cnt5 if (n == 1 && cnt2 <= cnt5) { // Return the minimum operations return 2 * cnt5 - cnt2; } // Otherwise, n can't be reduced else return -1; } // Driver Code int main() { // Given Number N int N = 25; // Function Call cout << minimumMoves(N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum number // operations required to reduce N to 1 static int minimumMoves(int n) { // Stores count of powers of 2 and 5 int cnt2 = 0, cnt5 = 0; // Calculating the primefactors 2 while (n % 2 == 0) { n /= 2; cnt2++; } // Calculating the primefactors 5 while (n % 5 == 0) { n /= 5; cnt5++; } // If n is 1 and cnt2 <= cnt5 if (n == 1 && cnt2 <= cnt5) { // Return the minimum operations return 2 * cnt5 - cnt2; } // Otherwise, n can't be reduced else return -1; } // Driver Code public static void main(String[] args) { // Given Number N int N = 25; // Function Call System.out.print(minimumMoves(N)); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to find the minimum number # operations required to reduce N to 1 def minimumMoves(n): # Stores count of powers of 2 and 5 cnt2 = 0 cnt5 = 0 # Calculating the primefactors 2 while (n % 2 == 0): n //= 2 cnt2 += 1 # Calculating the primefactors 5 while (n % 5 == 0): n //= 5 cnt5 += 1 # If n is 1 and cnt2 <= cnt5 if (n == 1 and cnt2 <= cnt5): # Return the minimum operations return 2 * cnt5 - cnt2 # Otherwise, n can't be reduced else: return -1 # Driver Code if __name__ == '__main__': # Given Number N N = 25 # Function Call print(minimumMoves(N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number // operations required to reduce N to 1 static int minimumMoves(int n) { // Stores count of powers of 2 and 5 int cnt2 = 0, cnt5 = 0; // Calculating the primefactors 2 while (n % 2 == 0) { n /= 2; cnt2++; } // Calculating the primefactors 5 while (n % 5 == 0) { n /= 5; cnt5++; } // If n is 1 and cnt2 <= cnt5 if (n == 1 && cnt2 <= cnt5) { // Return the minimum operations return 2 * cnt5 - cnt2; } // Otherwise, n can't be reduced else return -1; } // Driver Code public static void Main() { // Given Number N int N = 25; // Function Call Console.WriteLine(minimumMoves(N)); } } // This code is contributed by SURENDRA_GANGWAR
Javascript
<script> // Javascript program to implement // the above approach // Function to find the minimum number // operations required to reduce N to 1 function minimumMoves(n) { // Stores count of powers of 2 and 5 let cnt2 = 0, cnt5 = 0; // Calculating the primefactors 2 while (n % 2 == 0) { n /= 2; cnt2++; } // Calculating the primefactors 5 while (n % 5 == 0) { n /= 5; cnt5++; } // If n is 1 and cnt2 <= cnt5 if (n == 1 && cnt2 <= cnt5) { // Return the minimum operations return 2 * cnt5 - cnt2; } // Otherwise, n can't be reduced else return -1; } // Driver Code // Given Number N let N = 25; // Function Call document.write(minimumMoves(N)); </script>
4
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA