Dado un número entero N, la tarea es encontrar los pasos mínimos para visitar todos los números enteros en el rango [1, N] seleccionando cualquier número entero y saltando i pasos en cada i -ésimo salto.
Nota: es posible volver a visitar un número entero más de una vez.
Ejemplos:
Entrada: N = 6
Salida: 3
Explicación:
Una de las siguientes formas es:
Primero comience en el primer número y visite los enteros {1, 2, 4}.
Ahora comience en el segundo número y visite los enteros como {2, 3, 5}
Ahora comience en el último número y visítelo.
Por lo tanto, en un total de 3 pasos se pueden visitar todos los números en el rango [1, 6]. Y también es el número mínimo de pasos necesarios.Entrada: N = 4
Salida: 2
Enfoque ingenuo: el problema dado se puede resolver en función de las siguientes observaciones:
- En cada paso las dimensiones de los saltos aumentan, por eso algunos números se quedan sin visitar en un paso.
- Partiendo del primer número y realizando los saltos se puede observar que el tamaño máximo del salto es el número total de pasos necesarios para visitar cada número. Como en un movimiento, uno no puede visitar cada número entre dos números no visitados.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos count = 1 y res = 0.
- Recorra el rango [1, N] e incremente i por conteo y actualice res como res =max(res, conteo) e incremente conteo en 1 .
- Después de completar los pasos anteriores, imprima el res.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to find minimum steps
int minSteps(int N)
{
// Initialize count and result
int count = 1, res = 0;
// Traverse over the range [1, N]
for (int i = 1; i <= N; i += count) {
// Update res
res = max(res, count);
// Increment count
count++;
}
// Return res
return res;
}
// Driver Code
int main()
{
// Input
int N = 6;
// Function call
cout << minSteps(N) << "\n";
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Utility function to find minimum steps
static int minSteps(int N)
{
// Initialize count and result
int count = 1, res = 0;
// Traverse over the range [1, N]
for (int i = 1; i <= N; i += count)
{
// Update res
res = Math.max(res, count);
// Increment count
count++;
}
// Return res
return res;
}
// Driver Code
public static void main (String[] args)
{
// Input
int N = 6;
// Function call
System.out.println(minSteps(N) );
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 implementation of the above approach # Utility function to find minimum steps def minSteps(N): # Initialize count and result count = 1 res = 0 # Traverse over the range [1, N] for i in range(1, N + 1, count): # Update res res = max(res, count) # Increment count count += 1 # Return res return res # Driver Code if __name__ == '__main__': # Input N = 6 # Function call print(minSteps(N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Utility function to find minimum steps
static int minSteps(int N)
{
// Initialize count and result
int count = 1, res = 0;
// Traverse over the range [1, N]
for (int i = 1; i <= N; i += count)
{
// Update res
res = Math.Max(res, count);
// Increment count
count++;
}
// Return res
return res;
}
// Driver Code
public static void Main()
{
// Input
int N = 6;
// Function call
Console.Write(minSteps(N) );
}
}
Javascript
<script>
// JavaScript implementation of the above approach
// Utility function to find minimum steps
function minSteps(N) {
// Initialize count and result
let count = 1,
res = 0;
// Traverse over the range [1, N]
for (let i = 1; i <= N; i += count) {
// Update res
res = Math.max(res, count);
// Increment count
count++;
}
// Return res
return res;
}
// Driver Code
// Input
let N = 6;
// Function call
document.write(minSteps(N));
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: los pasos anteriores se pueden optimizar en función de las siguientes observaciones:
- Supongamos una array arr[] como arr[] ={1, 1, 2, 2, 2, 3, 3, 3, ….]. Ahora la idea es encontrar el número K que es el tamaño máximo de salto dado en un paso.
- En la array anterior, ya que 1 ocurre dos veces, 2 ocurre tres veces, 3 ocurre cuatro veces y así sucesivamente. ( K – 1) ocurriría K veces.
- Ahora, supongamos que K ocurre c veces, entonces el recuento total de ocurrencias debe ser igual a N.
- 2 + 3 + 4 +….+ K + c = N
- c = N – 2 – 3 – 4 -….- K …..(i)
- Entonces uno necesita encontrar la mayor ecuación que satisfaga K (i) también c≥1 , entonces
- K 2 + K – 2 × norte ≤ 0.
- Por lo tanto , K = (-1 + √(1 + 8 ×N)) / 2
Siga los pasos a continuación para resolver el problema:
- Imprime el valor (-1 + √(1 + 8 *N)) / 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to find minimum steps
int minSteps(int N)
{
int res = (sqrt(1 + 8 * N) - 1) / 2;
return res;
}
// Driver code
int main()
{
// Input integer
int N = 6;
// Function call
cout << minSteps(N) << "\n";
}
Java
// Java implementation of the above approach
import java.io.*;
import java.lang.Math;
class GFG{
// Utility function to find minimum steps
static int minSteps(int N)
{
int res = ((int)Math.sqrt(1 + 8 * N) - 1) / 2;
return res;
}
// Driver code
public static void main (String[] args)
{
// Input integer
int N = 6;
// Function call
System.out.println(minSteps(N) + "\n");
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python 3 implementation of the above approach from math import sqrt # Utility function to find minimum steps def minSteps(N): res = int((sqrt(1 + 8 * N) - 1) // 2) return res # Driver code if __name__ == '__main__': # Input integer N = 6 # Function call print(minSteps(N))
C#
// Java implementation of the above approach
using System;
class GFG
{
// Utility function to find minimum steps
static int minSteps(int N)
{
int res = ((int)Math.Sqrt(1 + 8 * N) - 1) / 2;
return res;
}
// Driver code
public static void Main (String[] args)
{
// Input integer
int N = 6;
// Function call
Console.Write(minSteps(N) + "\n");
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// javascript implementation of the above approach
// Utility function to find minimum steps
function minSteps(N)
{
var res = parseInt((Math.sqrt(1 + 8 * N) - 1) / 2);
return res;
}
// Driver code
// Input integer
var N = 6;
// Function call
document.write(minSteps(N));
// This code contributed by shikhasingrajput
</script>
3
Complejidad Temporal: O (1)
Espacio Auxiliar: O (1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA