Minimizar los pasos necesarios para alcanzar el valor N

Dada una recta numérica infinita del rango [-INFINITY, +INFINITY] y un número entero N , la tarea es encontrar el recuento mínimo de movimientos necesarios para llegar a N , comenzando desde 0 , ya sea moviendo i pasos hacia adelante o 1 pasos hacia atrás en cada i ^-ésimo movimiento.

Ejemplos:

Entrada: N = 18
Salida: 6
Explicación:
Para llegar al valor dado de N, realice las operaciones en la siguiente secuencia: 1 – 1 + 3 + 4 + 5 + 6 = 18
Por lo tanto, se requieren un total de 6 operaciones.

Entrada : N = 3
Salida: 2
Explicación:
Para llegar al valor dado de N, realice las operaciones en la siguiente secuencia: 1 + 2 = 3
Por lo tanto, se requieren un total de 2 operaciones.

Enfoque: La idea es inicialmente seguir sumando 1, 2, 3 . . . . K , hasta que sea mayor o igual al valor requerido N . Luego, calcule el número requerido que se restará de la suma actual. Siga los pasos a continuación para resolver el problema:

• Inicialmente, incremente en K hasta que N sea mayor que el valor actual. Ahora, deténgase en alguna posición 
  pos = 1 + 2 + …………. + pasos = pasos ∗ (pasos + 1) / 2 ≥ N.
  Nota: 0 ≤ pos – N < pasos . De lo contrario, el último paso no era posible.
  • Caso 1: Si pos = N entonces, ‘pasos’ es la respuesta requerida.
  • Caso 2: Si pos ≠ N , entonces reemplace cualquier iteración de K con -1.
• Al reemplazar cualquier K con -1 , el valor modificado de pos = pos – (K + 1) . Como K ∈ [1, pasos] , entonces pos ∈ [pos – pasos – 1, pos – 2] .
• Está claro que pos – paso < N . Si N < pos – 1 , elija el correspondiente K = pos – N – 1 y reemplace K con -1 y vaya directamente al punto N.
• Si N + 1 = pos , solo se requiere una operación -1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum steps
// required to reach N by either moving
// i steps forward or 1 steps backward
int minimumsteps(int N)
{
 
    // Stores the required count
    int steps = 0;
 
    // IF total moves required
    // is less than double of N
    while (steps * (steps + 1) < 2 * N) {
 
        // Update steps
        steps++;
    }
 
    // Steps required to reach N
    if (steps * (steps + 1) / 2 == N + 1) {
 
        // Update steps
        steps++;
    }
 
    cout << steps;
}
 
// Driver Code
int main()
{
 
    // Given value of N
    int N = 18;
    minimumsteps(N);
}

// Java program for the above approach
import java.util.*;
class GFG{
       
// Function to find the minimum steps
// required to reach N by either moving
// i steps forward or 1 steps backward
static void minimumsteps(int N)
{
 
    // Stores the required count
    int steps = 0;
 
    // IF total moves required
    // is less than double of N
    while (steps * (steps + 1) < 2 * N)
    {
 
        // Update steps
        steps++;
    }
 
    // Steps required to reach N
    if (steps * (steps + 1) / 2 == N + 1)
    {
 
        // Update steps
        steps++;
    }
 
    System.out.println(steps);
}
   
// Driver code
public static void main(String[] args)
{
   
    // Given value of N
    int N = 18;
    minimumsteps(N);
}
}
 
// This code is contributed by code_hunt.

# Function to find the minimum steps
# required to reach N by either moving
# i steps forward or 1 steps backward
 
def minimumsteps(N) :
 
    # Stores the required count
    steps = 0
 
    # IF total moves required
    # is less than double of N
    while (steps * (steps + 1) < 2 * N) :
 
        # Update steps
        steps += 1
 
    # Steps required to reach N
    if (steps * (steps + 1) / 2 == N + 1) :
 
        # Update steps
        steps += 1
    print(steps)
 
 
# Driver code
N = 18;
minimumsteps(N)
 
# This code is contributed by Dharanendra L V

// C# program for the above approach
using System;
 
class GFG {
 
    // Function to find the minimum steps
    // required to reach N by either moving
    // i steps forward or 1 steps backward
    static void minimumsteps(int N)
    {
 
        // Stores the required count
        int steps = 0;
 
        // IF total moves required
        // is less than double of N
        while (steps * (steps + 1) < 2 * N) {
 
            // Update steps
            steps++;
        }
 
        // Steps required to reach N
        if (steps * (steps + 1) / 2 == N + 1) {
 
            // Update steps
            steps++;
        }
 
        Console.WriteLine(steps);
    }
 
    // Driver code
    static public void Main()
    {
 
        // Given value of N
        int N = 18;
        minimumsteps(N);
    }
}
 
// This code is contributed by Dharanendra LV

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum steps
// required to reach N by either moving
// i steps forward or 1 steps backward
function minimumsteps(N)
{
     
    // Stores the required count
    let steps = 0;
 
    // IF total moves required
    // is less than double of N
    while (steps * (steps + 1) < 2 * N)
    {
         
        // Update steps
        steps++;
    }
 
    // Steps required to reach N
    if (steps * Math.floor((steps + 1) / 2) == N + 1)
    {
         
        // Update steps
        steps++;
    }
 
    document.write(steps);
}
 
// Driver Code
 
// Given value of N
let N = 18;
 
minimumsteps(N);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

6

CompleNidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)