Dado un número entero N , la tarea es contar los pasos mínimos necesarios para reducir el valor de N a 0 realizando las siguientes dos operaciones:
- Considere los números enteros A y B donde N = A * B (A != 1 y B != 1), reduzca N a min(A, B)
- Disminuye el valor de N en 1
Ejemplos:
Entrada: N = 3
Salida: 3
Explicación:
Los pasos involucrados son 3 -> 2 -> 1 -> 0
Por lo tanto, los pasos mínimos requeridos son 3.
Entrada: N = 4
Salida: 3
Explicación:
Los pasos involucrados son 4->2- >1->0.
Por lo tanto, los pasos mínimos requeridos son 3.
Enfoque Ingenuo: La idea es utilizar el concepto de Programación Dinámica. Siga los pasos a continuación para resolver el problema:
- La solución simple a este problema es reemplazar N con cada valor posible hasta que no sea 0.
- Cuando N llegue a 0, compare el conteo de movimientos con el mínimo obtenido hasta el momento para obtener la respuesta óptima.
- Finalmente, imprima los pasos mínimos calculados.
Ilustración:
norte = 4,
- Al aplicar la primera regla, los factores de 4 son [ 1, 2, 4 ].
Por lo tanto, todos los pares posibles ( a, b ) son ( 1 * 4), ( 2 * 2), ( 4 * 1).
El único par que cumple la condición ( a!=1 yb!=1) es (2, 2) . Por lo tanto, reduzca 4 a 2 .
Finalmente, reduzca N a 0 , en 3 pasos (4 -> 2 -> 1 -> 0)- Al aplicar la segunda regla, los pasos requeridos son 4 , (4 -> 3 -> 2 -> 1 -> 0).
Recursive tree for N = 4 is 4 / \ 3 2(2*2) | | 2 1 | | 1 0 | 0
- Por lo tanto, los pasos mínimos requeridos para reducir N a 0 son 3 .
Por lo tanto, la relación es:
f(N) = 1 + min( f(N-1), min(f(x)) ), donde N % x == 0 y x está en el rango [2, K] donde K = sqrt(N)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the minimum
// steps required to reduce n
int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Allocate memory for storing
// intermediate results
vector<int> dp(n + 1, -1);
// Store base values
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// Stores square root
// of each number
int sqr;
for (int i = 4; i <= n; i++) {
// Compute square root
sqr = sqrt(i);
int best = INT_MAX;
// Use rule 1 to find optimized
// answer
while (sqr > 1) {
// Check if it perfectly divides n
if (i % sqr == 0) {
best = min(best, 1 + dp[sqr]);
}
sqr--;
}
// Use of rule 2 to find
// the optimized answer
best = min(best, 1 + dp[i - 1]);
// Store computed value
dp[i] = best;
}
// Return answer
return dp[n];
}
// Driver Code
int main()
{
int n = 4;
cout << downToZero(n);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to count the minimum
// steps required to reduce n
static int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Allocate memory for storing
// intermediate results
int []dp = new int[n + 1];
for(int i = 0; i < n + 1; i++)
dp[i] = -1;
// Store base values
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// Stores square root
// of each number
int sqr;
for(int i = 4; i <= n; i++)
{
// Compute square root
sqr = (int)Math.sqrt(i);
int best = Integer.MAX_VALUE;
// Use rule 1 to find optimized
// answer
while (sqr > 1)
{
// Check if it perfectly divides n
if (i % sqr == 0)
{
best = Math.min(best, 1 + dp[sqr]);
}
sqr--;
}
// Use of rule 2 to find
// the optimized answer
best = Math.min(best, 1 + dp[i - 1]);
// Store computed value
dp[i] = best;
}
// Return answer
return dp[n];
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
System.out.print(downToZero(n));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to implement # the above approach import math import sys # Function to count the minimum # steps required to reduce n def downToZero(n): # Base case if (n <= 3): return n # Allocate memory for storing # intermediate results dp = [-1] * (n + 1) # Store base values dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 # Stores square root # of each number for i in range(4, n + 1): # Compute square root sqr = (int)(math.sqrt(i)) best = sys.maxsize # Use rule 1 to find optimized # answer while (sqr > 1): # Check if it perfectly divides n if (i % sqr == 0): best = min(best, 1 + dp[sqr]) sqr -= 1 # Use of rule 2 to find # the optimized answer best = min(best, 1 + dp[i - 1]) # Store computed value dp[i] = best # Return answer return dp[n] # Driver Code if __name__ == "__main__": n = 4 print(downToZero(n)) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count the minimum
// steps required to reduce n
static int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Allocate memory for storing
// intermediate results
int []dp = new int[n + 1];
for(int i = 0; i < n + 1; i++)
dp[i] = -1;
// Store base values
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// Stores square root
// of each number
int sqr;
for(int i = 4; i <= n; i++)
{
// Compute square root
sqr = (int)Math.Sqrt(i);
int best = int.MaxValue;
// Use rule 1 to find optimized
// answer
while (sqr > 1)
{
// Check if it perfectly divides n
if (i % sqr == 0)
{
best = Math.Min(best, 1 + dp[sqr]);
}
sqr--;
}
// Use of rule 2 to find
// the optimized answer
best = Math.Min(best, 1 + dp[i - 1]);
// Store computed value
dp[i] = best;
}
// Return answer
return dp[n];
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
Console.Write(downToZero(n));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to count the minimum
// steps required to reduce n
function downToZero(n)
{
// Base case
if (n <= 3)
return n;
// Allocate memory for storing
// intermediate results
let dp = new Array(n + 1)
dp.fill(-1);
// Store base values
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// Stores square root
// of each number
let sqr;
for (let i = 4; i <= n; i++) {
// Compute square root
sqr = Math.sqrt(i);
let best = Number.MAX_VALUE;
// Use rule 1 to find optimized
// answer
while (sqr > 1) {
// Check if it perfectly divides n
if (i % sqr == 0) {
best = Math.min(best, 1 + dp[sqr]);
}
sqr--;
}
// Use of rule 2 to find
// the optimized answer
best = Math.min(best, 1 + dp[i - 1]);
// Store computed value
dp[i] = best;
}
// Return answer
return dp[n];
}
let n = 4;
document.write(downToZero(n));
// This code is contributed by divyesh072019.
</script>
Producción:
3
Complejidad de tiempo: O(N * sqrt(n))
Espacio auxiliar: O(N)
Enfoque Eficiente: La idea es observar que es posible reemplazar N por N’ donde N’ = min(a, b) (N = a * b) (a != 1 yb != 1).
- Si N es par , entonces el valor más pequeño que divide a N es 2 . Por tanto, calcula directamente f(N) = 1 + f(2) = 3.
- Si N es impar , entonces reduzca N en 1 , es decir, N = N – 1 . Aplique la misma lógica que se usa para los números pares. Por lo tanto, para números impares, los pasos mínimos requeridos son 4 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// steps required to reduce n
int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Return answer based on
// parity of n
return n % 2 == 0 ? 3 : 4;
}
// Driver Code
int main()
{
int n = 4;
cout << downToZero(n);
return 0;
}
Java
// Java Program to implement
// the above approach
class GFG{
// Function to find the minimum
// steps required to reduce n
static int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Return answer based on
// parity of n
return n % 2 == 0 ? 3 : 4;
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
System.out.println(downToZero(n));
}
}
// This code is contributed by rock_cool
Python3
# Python3 Program to implement # the above approach # Function to find the minimum # steps required to reduce n def downToZero(n): # Base case if (n <= 3): return n; # Return answer based on # parity of n if(n % 2 == 0): return 3; else: return 4; # Driver Code if __name__ == '__main__': n = 4; print(downToZero(n)); # This code is contributed by Rohit_ranjan
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to find the minimum
// steps required to reduce n
static int downToZero(int n)
{
// Base case
if (n <= 3)
return n;
// Return answer based on
// parity of n
return n % 2 == 0 ? 3 : 4;
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
Console.WriteLine(downToZero(n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to find the minimum
// steps required to reduce n
function downToZero(n)
{
// Base case
if (n <= 3)
return n;
// Return answer based on
// parity of n
return n % 2 == 0 ? 3 : 4;
}
let n = 4;
document.write(downToZero(n));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
3
Complejidad temporal: O(1)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por skallole01 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA