Dado un número entero N , la tarea es encontrar el número mínimo de pasos para obtener N de M ( M = 1 inicialmente). En cada paso, M/X se puede sumar a M , donde X es cualquier número entero positivo.
Ejemplos:
Entrada : N = 5
Salida: 3
Explicación: Inicialmente, el número es 1. Se agrega 1/1 para convertirlo en 2.
En el siguiente paso, al agregar 2/1 = 2, se convierte en 4. Por último, agregue 4/4 = 1 para obtener el 5.
Estos son los pasos mínimos necesarios para convertir 1 a 5Entrada : N = 7
Salida: 4
Explicación: Inicialmente el número es 1.
Ahora se le suma 1/1 y se convierte en 2.
Después de sumar 2/1 = 2 se convierte en 4. En el tercero se suma 4/2 = 2 y se convierte en 6.
En el paso final suma 6/6 = 1 y se convierte en 7.
Enfoque: El enfoque de esta pregunta es usando Programación Dinámica . Para cada número entero, hay muchos movimientos posibles. Almacene los pasos mínimos requeridos para llegar a cada número en la array dp[] y utilícelos para los siguientes números. Siga los pasos que se mencionan a continuación.
- Comience a iterar de 2 a N .
- Para cada número i , haga lo siguiente:
- Comprueba a partir de qué números (menores que i ) podemos llegar a i .
- Ahora, para esos números, encuentre los pasos mínimos requeridos para llegar a i usando la relación dp[i] = min(dp[i], dp[j]+1) donde j es un número desde donde se puede llegar a i .
- Almacene ese valor mínimo en la array dp[i] .
- Después de que se realiza la iteración para todos los elementos hasta el valor de retorno N de dp[N].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum steps required
int minSteps(int N)
{
vector<int> dp(N + 1, INT_MAX);
dp[1] = 0;
// Loop to find the minimum steps to
// reach N from 1
for (int i = 2; i <= N; ++i) {
for (int j = 1; j <= i; ++j) {
// Finding the distance
// between two numbers
int distance = i - j;
if (distance == 0) {
continue;
}
// Divide the number
int divide = j / distance;
if (divide != 0) {
// Checking if the number
// can be reached or not
if (j / divide == distance) {
dp[i] = min(dp[j] + 1, dp[i]);
}
}
}
}
return dp[N];
}
// Driver code
int main()
{
int N = 7;
int ans = minSteps(N);
cout << (ans);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java code to implement above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the minimum steps required
static int minSteps(int N)
{
int dp[] = new int[N + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[1] = 0;
// Loop to find the minimum steps to
// reach N from 1
for (int i = 2; i <= N; ++i) {
for (int j = 1; j <= i; ++j) {
// Finding the distance
// between two numbers
int distance = i - j;
if (distance == 0) {
continue;
}
// Divide the number
int divide = j / distance;
if (divide != 0) {
// Checking if the number
// can be reached or not
if (j / divide == distance) {
dp[i]
= Math.min(dp[j] + 1,
dp[i]);
}
}
}
}
return dp[N];
}
// Driver code
public static void main(String[] args)
{
int N = 7;
int ans = minSteps(N);
System.out.println(ans);
}
}
Python
# Python] code to implement above approach import sys # Function to find the minimum steps required def minSteps(N): dp = [] dp = [sys.maxsize for i in range(N + 1)] dp[1] = 0; # Loop to find the minimum steps to # reach N from 1 for i in range(2, N + 1): for j in range(1, i + 1): # Finding the distance # between two numbers distance = i - j if (distance == 0): continue # Divide the number divide = j // distance; if (divide != 0): # Checking if the number # can be reached or not if (j // divide == distance): dp[i] = min(dp[j] + 1, dp[i]) return dp[N] # Driver code N = 7 ans = minSteps(N); print(ans) # This code is contributed by Samim Hossain Mondal.
C#
// C# program for the above approach
using System;
public class GFG{
// Function to find the minimum steps required
static int minSteps(int N)
{
int[] dp = new int[N + 1];
for(int i = 0; i < N + 1; i++)
dp[i] = Int32.MaxValue;
dp[1] = 0;
// Loop to find the minimum steps to
// reach N from 1
for (int i = 2; i <= N; ++i) {
for (int j = 1; j <= i; ++j) {
// Finding the distance
// between two numbers
int distance = i - j;
if (distance == 0) {
continue;
}
// Divide the number
int divide = j / distance;
if (divide != 0) {
// Checking if the number
// can be reached or not
if (j / divide == distance) {
dp[i]
= Math.Min(dp[j] + 1,
dp[i]);
}
}
}
}
return dp[N];
}
// Driver code
static public void Main (){
int N = 7;
int ans = minSteps(N);
Console.Write(ans);
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the minimum steps required
function minSteps( N)
{
let dp = new Array(N + 1).fill(Number.MAX_VALUE);
dp[1] = 0;
// Loop to find the minimum steps to
// reach N from 1
for (let i = 2; i <= N; ++i) {
for (let j = 1; j <= i; ++j) {
// Finding the distance
// between two numbers
let distance = i - j;
if (distance == 0) {
continue;
}
// Divide the number
let divide =Math.floor(j / distance);
if (divide != 0) {
// Checking if the number
// can be reached or not
if (j / divide == distance) {
dp[i] = Math.min(dp[j] + 1, dp[i]);
}
}
}
}
return dp[N];
}
// Driver code
let N = 7;
let ans = minSteps(N);
document.write((ans));
// This code is contributed by Potta Lokesh
</script>
4
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA