Encuentre movimientos mínimos para alcanzar el objetivo en una línea infinita

Dada una posición de destino en la recta numérica infinita, es decir, -infinito a +infinito. Comenzando desde 0 tienes que alcanzar el objetivo moviéndote como se describe: En un enésimo movimiento puedes dar i pasos hacia adelante o hacia atrás. Encuentre el número mínimo de movimientos necesarios para alcanzar el objetivo.
Ejemplos: 
 

Input : target = 3
Output : 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Hemos discutido una solución recursiva ingenua en la publicación a continuación. 
Pasos mínimos para llegar a un destino
Si el objetivo es negativo, podemos tomarlo como positivo porque partimos de 0 de forma simétrica. 
La idea es moverse en una dirección el mayor tiempo posible, esto dará movimientos mínimos. Comenzando en 0, el primer movimiento nos lleva a la posición 1, el segundo movimiento nos lleva a la posición 3 (1+2), el tercer movimiento nos lleva a la posición 6 (1+2+3), y así sucesivamente; Entonces, para encontrar el objetivo, seguimos agregando movimientos hasta que encontramos el enésimo movimiento tal que 1+2+3+…+n>=objetivo. Ahora, si la suma (1+2+3+…+n) es igual al objetivo, nuestro trabajo está hecho, es decir, necesitaremos n movimientos para alcanzar el objetivo. Ahora, el siguiente caso donde la suma es mayor que el objetivo . Encuentre la diferencia por cuánto estamos adelante, es decir, suma – objetivo. Sea la diferencia d = suma – objetivo. 
Si tomamos el i-ésimo movimiento hacia atrás, la nueva suma se convertirá en (suma – 2i), es decir, 1+2+3+…-x+x+1…+n. Ahora, si sum-2i = objetivo, entonces nuestro trabajo está hecho. Dado que sum – target = 2i, es decir, la diferencia debe ser par, ya que obtendremos un número entero i que dará la respuesta. Entonces surgen los siguientes casos. 
Caso 1: La diferencia es par, entonces la respuesta es n, (porque siempre obtendremos un movimiento invertido que conducirá al objetivo). 
Caso 2: la diferencia es impar, luego damos un paso más, es decir, sumamos n+1 a la suma y ahora nuevamente tomamos la diferencia. Si la diferencia es par, el n+1 es la respuesta, de lo contrario, tendríamos que hacer un movimiento más y esto sin duda marcará la diferencia, incluso entonces la respuesta será n+2.
Explicación: Dado que la diferencia es impar. El objetivo es par o impar. 
caso 1: n es par (1+2+3+…+n) entonces sumando n+1 hace que la diferencia sea pareja. 
caso 2: n es impar, entonces sumar n+1 no hace la diferencia, incluso así tendríamos que hacer un movimiento más, entonces n+2.
Ejemplo: 
objetivo = 5. 
Seguimos realizando movimientos hasta que alcanzamos el objetivo o simplemente lo cruzamos. 
suma = 1 + 2 + 3 = 6 > 5, paso = 3. 
Diferencia = 6 – 5 = 1. Dado que la diferencia es un valor impar, no alcanzaremos el objetivo cambiando cualquier movimiento de +i a -i. Así que aumentamos nuestro paso. Necesitamos aumentar el paso en 2 para obtener una diferencia uniforme (ya que n es impar y el objetivo también es impar). Ahora que tenemos una diferencia uniforme, podemos simplemente cambiar cualquier movimiento a la izquierda (es decir, cambiar + a -) siempre que la suma del valor cambiado sea igual a la mitad de la diferencia. Podemos cambiar 1 y 4 o 2 y 3 o 5. 
 

// CPP program to find minimum moves to
// reach target if we can move i steps in
// i-th move.
#include <iostream>
using namespace std;
 
int reachTarget(int target)
{
    // Handling negatives by symmetry
    target = abs(target);
     
    // Keep moving while sum is smaller or difference
    // is odd.
    int sum = 0, step = 0;
    while (sum < target || (sum - target) % 2 != 0) {
        step++;
        sum += step;
    }
    return step;
}
 
// Driver code
int main()
{
    int target = 5;
    cout << reachTarget(target);
    return 0;
}

// Java program to find minimum 
//moves to reach target if we can
// move i steps in i-th move.
import java.io.*;
import java.math.*;
 
class GFG {
     
    static int reachTarget(int target)
    {
        // Handling negatives by symmetry
        target = Math.abs(target);
         
        // Keep moving while sum is smaller
        // or difference is odd.
        int sum = 0, step = 0;
         
        while (sum < target || (sum - target) % 2
                                        != 0) {
            step++;
            sum += step;
        }
        return step;
    }
     
    // Driver code
    public static void main(String args[])
    {
       int target = 5;
       System.out.println(reachTarget(target));
    }
}
 
// This code is contributed by Nikita tiwari.

# Python 3 program to find minimum 
# moves to reach target if we can
# move i steps in i-th move.
 
 
def reachTarget(target) :
 
    # Handling negatives by symmetry
    target = abs(target)
     
    # Keep moving while sum is
    # smaller or difference is odd.
    sum = 0
    step = 0
    while (sum < target or (sum - target) %
                                  2 != 0) :
        step = step + 1
        sum = sum + step
     
    return step
     
 
# Driver code
target = 5
print(reachTarget(target))
 
 
# This code is contributed by Nikita Tiwari

// C# program to find minimum
//moves to reach target if we can
// move i steps in i-th move.
using System;
 
class GFG {
     
    static int reachTarget(int target)
    {
        // Handling negatives by symmetry
        target = Math.Abs(target);
         
        // Keep moving while sum is smaller
        // or difference is odd.
        int sum = 0, step = 0;
         
        while (sum < target ||
              (sum - target) % 2!= 0)
        {
            step++;
            sum += step;
        }
        return step;
    }
     
    // Driver code
    public static void Main()
    {
    int target = 5;
    Console.WriteLine(reachTarget(target));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find 
// minimum moves to reach
// target if we can move i
// steps in i-th move.
 
function reachTarget($target)
{
    // Handling negatives
    // by symmetry
    $target = abs($target);
     
    // Keep moving while sum is
    // smaller or difference is odd.
    $sum = 0; $step = 0;
    while ($sum < $target or
          ($sum - $target) % 2 != 0)
          {
            $step++;
            $sum += $step;
          }
    return $step;
}
 
// Driver code
$target = 5;
echo reachTarget($target);
 
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript program to find minimum 
//moves to reach target if we can
// move i steps in i-th move.
 
function reachTarget(target)
    {
        // Handling negatives by symmetry
        target = Math.abs(target);
           
        // Keep moving while sum is smaller
        // or difference is odd.
        let sum = 0, step = 0;
           
        while (sum < target || (sum - target) % 2
                                        != 0) {
            step++;
            sum += step;
        }
        return step;
    }
 
// Driver code
 
    let target = 5;
      document.write(reachTarget(target));
 
</script>

Producción : 

5

Complejidad Temporal: O(n), donde n es el número de pasos 
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.