Dado un número entero N , la tarea es encontrar el número mínimo de pasos para llegar al número N desde 1 multiplicando cada paso por 2, 3, 4 o 5. Si no es posible llegar a N, imprima -1.
Ejemplos:
Entrada: N = 10
Salida: 2
Explicación:
Número inicial = 1
Paso 1: Multiplícalo por 2, Número actual = 2
Paso 2: Multiplícalo por 5, Número actual = 10
Por lo tanto, se requieren al menos 2 pasos para llegar a 10.
Entrada: N = 13
Salida: -1
Explicación:
No hay forma de llegar a 13 usando ninguna operación dada
Enfoque: La idea es usar el algoritmo Greedy para elegir la operación que se debe realizar en cada paso y realizar las operaciones de manera inversa, es decir, en lugar de ir de 1 a N, encuentre las operaciones requeridas para llegar a N a 1. A continuación se muestra la ilustración de los pasos:
- Aplique las siguientes operaciones hasta que N sea mayor que 1.
- Compruebe si N es divisible por 5, luego aumente los pasos en 1 y reduzca N a N/5
- De lo contrario, verifique si N es divisible por 4, luego aumente los pasos en 1 y reduzca N a N/4
- De lo contrario, verifique si N es divisible por 3, luego aumente los pasos en 1 y reduzca N a N/3
- De lo contrario, verifique si N es divisible por 2, luego aumente los pasos en 1 y reduzca N a N / 2
- Si en algún paso no se puede aplicar ninguna operación, entonces no hay un conjunto posible de operaciones para llegar a N desde 1. Por lo tanto, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// minimum number of steps
// to reach N from 1
#include <bits/stdc++.h>
using namespace std;
// Function to find a minimum number
// of steps to reach N from 1
int Minsteps(int n)
{
int ans = 0;
// Check until N is greater
// than 1 and operations
// can be applied
while (n > 1) {
// Condition to choose the
// operations greedily
if (n % 5 == 0) {
ans++;
n = n / 5;
continue;
}
else if (n % 4 == 0) {
ans++;
n = n / 4;
continue;
}
else if (n % 3 == 0) {
ans++;
n = n / 3;
continue;
}
else if (n % 2 == 0) {
ans++;
n = n / 2;
continue;
}
return -1;
}
return ans;
}
// Driver code
int main()
{
int n = 10;
cout << Minsteps(n);
return 0;
}
Java
// Java implementation to find
// minimum number of steps
// to reach N from 1
import java.util.*;
class GFG{
// Function to find a minimum number
// of steps to reach N from 1
static int Minsteps(int n)
{
int ans = 0;
// Check until N is greater
// than 1 and operations
// can be applied
while (n > 1)
{
// Condition to choose the
// operations greedily
if (n % 5 == 0)
{
ans++;
n = n / 5;
continue;
}
else if (n % 4 == 0)
{
ans++;
n = n / 4;
continue;
}
else if (n % 3 == 0)
{
ans++;
n = n / 3;
continue;
}
else if (n % 2 == 0)
{
ans++;
n = n / 2;
continue;
}
return -1;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 10;
System.out.print(Minsteps(n));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation to find # minimum number of steps # to reach N from 1 # Function to find a minimum number # of steps to reach N from 1 def Minsteps(n): ans = 0 # Check until N is greater # than 1 and operations # can be applied while (n > 1): # Condition to choose the # operations greedily if (n % 5 == 0): ans = ans + 1 n = n / 5 continue elif (n % 4 == 0): ans = ans + 1 n = n / 4 continue elif (n % 3 == 0): ans = ans + 1 n = n / 3 continue elif (n % 2 == 0): ans = ans + 1 n = n / 2 continue return -1 return ans # Driver code n = 10 print(Minsteps(n)) # This code is contributed by Pratik
C#
// C# implementation to find
// minimum number of steps
// to reach N from 1
using System;
class GFG{
// Function to find a minimum number
// of steps to reach N from 1
static int Minsteps(int n)
{
int ans = 0;
// Check until N is greater
// than 1 and operations
// can be applied
while (n > 1)
{
// Condition to choose the
// operations greedily
if (n % 5 == 0)
{
ans++;
n = n / 5;
continue;
}
else if (n % 4 == 0)
{
ans++;
n = n / 4;
continue;
}
else if (n % 3 == 0)
{
ans++;
n = n / 3;
continue;
}
else if (n % 2 == 0)
{
ans++;
n = n / 2;
continue;
}
return -1;
}
return ans;
}
// Driver code
public static void Main()
{
int n = 10;
Console.Write(Minsteps(n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to find
// minimum number of steps
// to reach N from 1
// Function to find a minimum number
// of steps to reach N from 1
function Minsteps(n)
{
var ans = 0;
// Check until N is greater
// than 1 and operations
// can be applied
while (n > 1)
{
// Condition to choose the
// operations greedily
if (n % 5 == 0)
{
ans++;
n = n / 5;
continue;
}
else if (n % 4 == 0)
{
ans++;
n = n / 4;
continue;
}
else if (n % 3 == 0)
{
ans++;
n = n / 3;
continue;
}
else if (n % 2 == 0)
{
ans++;
n = n / 2;
continue;
}
return -1;
}
return ans;
}
// Driver code
var n = 10;
// Function Call
document.write(Minsteps(n));
// This code is contributed by Khushboogoyal499
</script>
Producción:
2
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)