Dada una posición objetivo en la recta numérica infinita, (-infinito a +infinito). Comenzando desde 0, debe alcanzar el objetivo moviéndose como se describe: En el i-ésimo movimiento, puede 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.
Acercarse :
La idea es similar a la discutida en el enfoque O(n) aquí .
Siga agregando suma = 1 + 2 + .. + n >= objetivo. Resolver esta ecuación cuadrática da el n más pequeño tal que suma >= objetivo, es decir, resolver para n en n(n+1) / 2 – objetivo >= 0 da el n más pequeño.
Si suma == objetivo, la respuesta es n. Ahora el siguiente caso donde la suma es mayor que el objetivo. Encuentre la diferencia por cuántos pasos el índice está por delante del objetivo, es decir, suma — objetivo.
Caso 1: La diferencia es incluso entonces la respuesta es n, (porque siempre habrá un cambio de movimiento que conducirá al objetivo).
Caso 2: la diferencia es impar, luego da un paso más, es decir, agrega n+1 a la suma y ahora vuelve a tomar la diferencia. Si la diferencia es par, el n+1 es la respuesta; de lo contrario, haga 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), luego sumar n + 1 hace que la diferencia sea pareja.
Caso 2: n es impar, entonces sumar n + 1 no hace la diferencia, aun así, haga un movimiento más, es decir, n+2.
C++
// CPP code to find minimum moves
// to reach target
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum steps
// to reach target
int StepstoReachTarget(int target)
{
// Handling negatives
// by symmetry
target = abs(target);
// Keep moving while sum is
// smaller i.e calculating n
int n = ceil((-1.0 + sqrt(1 + 8.0 * target)) / 2);
int sum = n * (n + 1) / 2;
if (sum == target)
return n;
int d = sum - target;
// case 1 : d is even
if ((d & 1) == 0)
return n;
// d is odd
else
return n + ((n & 1) ? 2 : 1);
}
// Driver code
int main()
{
int target = 5;
// Function call
cout << StepstoReachTarget(target);
return 0;
}
Java
// Java code to find minimum moves
// to reach target
import java.lang.*;
class GFG {
// Function to find minimum steps
// to reach target
static int StepstoReachTarget(int target)
{
// Handling negatives
// by symmetry
target = Math.abs(target);
// Keep moving while sum is
// smaller i.e calculating n
int n = (int)Math.ceil(
(-1.0 + (int)Math.sqrt(1 + 8.0 * target)) / 2);
int sum = n * (n + 1) / 2;
if (sum == target)
return n;
int d = sum - target;
// case 1 : d is even
if ((d & 1) == 0)
return n;
// d is odd
else
return n + ((n & 1) != 0 ? 2 : 1);
}
// Driver code
public static void main(String[] arg)
{
int target = 5;
// Function call
System.out.println(StepstoReachTarget(target));
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
# Python code to find minimum # moves to reach target import math # Function to find minimum # steps to reach target def StepstoReachTarget(target): # Handling negatives # by symmetry target = abs(target) # Keep moving while sum is # smaller i.e calculating n n = math.ceil((-1.0 + math.sqrt(1 + 8.0 * target)) / 2) sum = n * (n + 1) / 2 if (sum == target): return n d = sum - target # case 1 : d is even if ((int(d) & 1) == 0): return n # d is odd else: if(int(d) & 1): return n + 2 return n + 1 # Driver code target = 5 # Function call print(StepstoReachTarget(target)) # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# code to find minimum moves
// to reach target
using System;
class GFG {
// Function to find minimum steps
// to reach target
static int StepstoReachTarget(int target)
{
// Handling negatives
// by symmetry
target = Math.Abs(target);
// Keep moving while sum is
// smaller i.e calculating n
int n = (int)Math.Ceiling(
(-1.0 + (int)Math.Sqrt(1 + 8.0 * target)) / 2);
int sum = n * (n + 1) / 2;
if (sum == target)
return n;
int d = sum - target;
// case 1 : d is even
if ((d & 1) == 0)
return n;
// d is odd
else
return n + ((n & 1) != 0 ? 2 : 1);
}
// Driver code
public static void Main()
{
int target = 5;
// Function call
Console.Write(StepstoReachTarget(target));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP code to find minimum
// moves to reach target
// Function to find minimum
// steps to reach target
function StepstoReachTarget($target)
{
// Handling negatives$
// by symmetry$
$target = abs($target);
// Keep moving while sum is
// smaller i.e calculating n
$n = ceil((-1.0 + sqrt(1 +
8.0 * $target)) / 2);
$sum = $n * ($n + 1) / 2;
if ($sum == $target)
return $n;
$d = $sum - $target;
// case 1 : d is even
if (($d & 1) == 0)
return n;
// d is odd
else
return $n + (($n & 1) ? 2 : 1);
}
// Driver code
$target = 5;
// Function call
echo StepstoReachTarget($target);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find minimum moves
// to reach target
// Function to find minimum steps
// to reach target
function StepstoReachTarget(target)
{
// Handling negatives
// by symmetry
target = Math.abs(target);
// Keep moving while sum is
// smaller i.e calculating n
let n = Math.ceil((-1.0 +
Math.sqrt(1 + 8.0 * target)) / 2);
let sum = n * (n + 1) / 2;
if (sum == target)
return n;
let d = sum - target;
// Case 1 : d is even
if ((d & 1) == 0)
return n;
// d is odd
else
return n + ((n & 1) != 0 ? 2 : 1);
}
// Driver Code
let target = 5;
// Function call
document.write(StepstoReachTarget(target));
// This code is contributed by avijitmondal1998
</script>
5
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)