Encuentra el número de saltos para llegar a X en la recta numérica desde cero

Dado un entero X. La tarea es encontrar el número de saltos para llegar a un punto X en la recta numérica a partir de cero. 
Nota : El primer salto realizado puede tener una longitud de una unidad y cada salto sucesivo será exactamente una unidad más largo que el salto anterior en longitud. Se permite ir a la izquierda o a la derecha en cada salto. 
Ejemplos: 
 

Input : X = 8
Output : 4
Explanation : 
0 -> -1 -> 1 -> 4-> 8 are possible stages.

Input : X = 9
Output : 5
Explanation : 
0 -> -1 -> -3 -> 0 -> 4-> 9 are 
possible stages

Enfoque : Observando con atención, se puede decir fácilmente que: 
 

• Si siempre has saltado en la dirección correcta, después de n saltos estarás en el punto p = 1 + 2 + 3 + 4 + … + n.
• En cualquiera de estos n saltos, si en lugar de saltar a la derecha, saltas a la izquierda en el k-ésimo salto (k<=n), estarías en el punto p – 2k .
• Además, al elegir cuidadosamente qué saltos ir a la izquierda y cuáles a la derecha, después de n saltos, puede estar en cualquier punto entre n * (n + 1) / 2 y – (n * (n + 1) / 2) con la misma paridad que n * (n + 1) / 2.

Teniendo en cuenta los puntos anteriores, lo que debes hacer es simular el proceso de salto, saltando siempre hacia la derecha, y si en algún momento has llegado a un punto que tiene la misma paridad que X y está en o más allá de X, Tendré tu respuesta.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the number of jumps
// to reach X in the number line from zero
 
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to calculate sum
// of numbers from 1 to x
int getsum(int x)
{
    return (x * (x + 1)) / 2;
}
 
// Function to find the number of jumps
// to reach X in the number line from zero
int countJumps(int n)
{
    // First make number positive
    // Answer will be same either it is
    // Positive or negative
    n = abs(n);
 
    // To store required answer
    int ans = 0;
 
    // Continue till number is lesser or not in same parity
    while (getsum(ans) < n or (getsum(ans) - n) & 1)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int n = 9;
 
    cout << countJumps(n);
 
    return 0;
}

// Java program to find the number of jumps
// to reach X in the number line from zero
 
class GFG
{
     
// Utility function to calculate sum
// of numbers from 1 to x
static int getsum(int x)
{
    return (x * (x + 1)) / 2;
}
 
// Function to find the number of jumps
// to reach X in the number line from zero
static int countJumps(int n)
{
    // First make number positive
    // Answer will be same either it is
    // Positive or negative
    n = Math.abs(n);
 
    // To store required answer
    int ans = 0;
 
    // Continue till number is lesser
    // or not in same parity
    while (getsum(ans) < n ||
         ((getsum(ans) - n) & 1) > 0)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int n = 9;
 
    System.out.println(countJumps(n));
}
}
 
// This code is contributed by Ryuga

# Python 3 program to find the number of jumps
# to reach X in the number line from zero
 
# Utility function to calculate sum
# of numbers from 1 to x
def getsum(x):
    return int((x * (x + 1)) / 2)
 
# Function to find the number of jumps
# to reach X in the number line from zero
def countJumps(n):
     
    # First make number positive
    # Answer will be same either it is
    # Positive or negative
    n = abs(n)
 
    # To store the required answer
    ans = 0
 
    # Continue till number is lesser
    # or not in same parity
    while (getsum(ans) < n or
          (getsum(ans) - n) & 1):
        ans += 1
 
    # Return the required answer
    return ans
 
# Driver code
if __name__ == '__main__':
    n = 9
 
    print(countJumps(n))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find the number of jumps
// to reach X in the number line from zero
using System;
 
class GFG
{
     
// Utility function to calculate sum
// of numbers from 1 to x
static int getsum(int x)
{
    return (x * (x + 1)) / 2;
}
 
// Function to find the number of jumps
// to reach X in the number line from zero
static int countJumps(int n)
{
    // First make number positive
    // Answer will be same either it is
    // Positive or negative
    n = Math.Abs(n);
 
    // To store required answer
    int ans = 0;
 
    // Continue till number is lesser or not in same parity
    while (getsum(ans) < n || ((getsum(ans) - n) & 1)>0)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
static void Main()
{
    int n = 9;
 
    Console.WriteLine(countJumps(n));
}
}
 
// This code is contributed by mits

<?php
// PHP program to find the number of jumps
// to reach X in the number line from zero
 
// Utility function to calculate sum
// of numbers from 1 to x
function getsum($x)
{
    return ($x * ($x + 1)) / 2;
}
 
// Function to find the number of jumps
// to reach X in the number line from zero
function countJumps($n)
{
    // First make number positive
    // Answer will be same either it is
    // Positive or negative
    $n = abs($n);
 
    // To store required answer
    $ans = 0;
 
    // Continue till number is lesser
    // or not in same parity
    while (getsum($ans) < $n or
          (getsum($ans) - $n) & 1)
        $ans++;
 
    // Return the required answer
    return $ans;
}
 
// Driver code
$n = 9;
 
echo countJumps($n);
 
// This code is contributed by Akanksha Rai
?>

<script>
 
// Javascript program to find the number of jumps
// to reach X in the number line from zero
 
// Utility function to calculate sum
// of numbers from 1 to x
function getsum(x)
{
    return (x * (x + 1)) / 2;
}
   
// Function to find the number of jumps
// to reach X in the number line from zero
function countJumps(n)
{
    // First make number positive
    // Answer will be same either it is
    // Positive or negative
    n = Math.abs(n);
   
    // To store required answer
    let ans = 0;
   
    // Continue till number is lesser
    // or not in same parity
    while (getsum(ans) < n ||
         ((getsum(ans) - n) & 1) > 0)
        ans++;
   
    // Return the required answer
    return ans;
}    
     
// Driver Code
 
      let n = 9;
   
    document.write(countJumps(n));
           
</script>

5

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)