Pasos mínimos para llegar a un destino

Dada una recta numérica de -infinito a +infinito. Comienzas en 0 y puedes ir hacia la izquierda o hacia la derecha. La condición es que en el i’ésimo movimiento, des i pasos. 

1. Encuentra si puedes llegar a un número dado x 
2. Encuentre la forma más óptima de llegar a un número x dado, si es que podemos alcanzarlo. Por ejemplo, se puede llegar a 3 en 2 pasos, (0, 1) (1, 3) y se puede llegar a 4 en 3 pasos (0, -1), (-1, 1) (1, 4).

Fuente: pregunta de la entrevista de Flipkart

Lo importante a tener en cuenta es que podemos llegar a cualquier destino, ya que siempre es posible hacer un movimiento de longitud 1. En cualquier paso i, podemos avanzar i, luego retroceder i + 1.
A continuación se muestra una solución recursiva sugerida por Arpit Thapar aquí _ 

1. Dado que la distancia de + 5 y – 5 desde 0 es la misma, encontramos la respuesta para el valor absoluto del destino.
2. Usamos una función recursiva que toma como argumentos: 
   1. Vértice de origen 
   2. Valor del último paso dado 
   3. Destino
3.  Si en algún punto origen vértice = destino; devolver el número de pasos.
4. De lo contrario, podemos ir en las dos direcciones posibles. Tome el mínimo de pasos en ambos casos.
   • Desde cualquier vértice podemos ir a: 
     • (fuente actual + último paso +1) y 
     • (fuente actual – último paso -1)
5. Si en algún punto, el valor absoluto de nuestra posición excede el valor absoluto de nuestro destino, entonces es intuitivo que el camino más corto no es posible desde aquí. Por lo tanto, hacemos el valor de los pasos INT_MAX, de modo que cuando tomo el mínimo de ambas posibilidades, esta se elimina. 

Si no usamos este último paso, el programa entra en una recursión INFINITA y da ERROR DE TIEMPO DE EJECUCIÓN.

A continuación se muestra la implementación de la idea anterior. Tenga en cuenta que la solución solo cuenta los pasos. 

// C++ program to count number of
// steps to reach a point
#include<bits/stdc++.h>
using namespace std;
 
// Function to count number of steps
// required to reach a destination
 
// source -> source vertex
// step -> value of last step taken
// dest -> destination vertex
int steps(int source, int step, int dest)
{
    // base cases
    if (abs(source) > (dest))
         return INT_MAX;
    if (source == dest) return step;
 
    // at each point we can go either way
 
    // if we go on positive side
    int pos = steps(source + step + 1,
                      step + 1, dest);
 
    // if we go on negative side
    int neg = steps(source - step - 1,
                      step + 1, dest);
 
    // minimum of both cases
    return min(pos, neg);
}
 
// Driver code
int main()
{
    int dest = 11;
    cout << "No. of steps required to reach "
                            << dest << " is "
                        << steps(0, 0, dest);
    return 0;
}

// Java program to count number of
// steps to reach a point
import java.io.*;
 
class GFG
{
 
    // Function to count number of steps
    // required to reach a destination
     
    // source -> source vertex
    // step -> value of last step taken
    // dest -> destination vertex
    static int steps(int source, int step,
                                int dest)
    {
        // base cases
        if (Math.abs(source) > (dest))
            return Integer.MAX_VALUE;
     
        if (source == dest)
            return step;
 
        // at each point we can go either way
 
        // if we go on positive side
        int pos = steps(source + step + 1,
                        step + 1, dest);
 
        // if we go on negative side
        int neg = steps(source - step - 1,
                        step + 1, dest);
 
        // minimum of both cases
        return Math.min(pos, neg);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int dest = 11;
        System.out.println("No. of steps required"+
                                " to reach " + dest +
                       " is " + steps(0, 0, dest));
    }
}
 
// This code is contributed by Prerna Saini

# python program to count number of
# steps to reach a point
import sys
 
# Function to count number of steps
# required to reach a destination
     
# source -> source vertex
# step -> value of last step taken
# dest -> destination vertex
def steps(source, step, dest):
     
    #base cases
    if (abs(source) > (dest)) :
        return sys.maxsize
     
    if (source == dest):
        return step
 
    # at each point we can go
    # either way
 
    # if we go on positive side
    pos = steps(source + step + 1,
                    step + 1, dest)
 
    # if we go on negative side
    neg = steps(source - step - 1,
                    step + 1, dest)
 
    # minimum of both cases
    return min(pos, neg)
     
 
# Driver Code
dest = 11;
print("No. of steps required",
               " to reach " ,dest ,
        " is " , steps(0, 0, dest));
     
 
# This code is contributed by Sam007.

// C# program to count number of
// steps to reach a point
using System;
 
class GFG
{
    // Function to count number of steps
    // required to reach a destination
     
    // source -> source vertex
    // step -> value of last step taken
    // dest -> destination vertex
    static int steps(int source, int step,
                                int dest)
    {
        // base cases
        if (Math.Abs(source) > (dest))
            return int.MaxValue;
     
        if (source == dest)    
            return step;
 
        // at each point we can go either way
 
        // if we go on positive side
        int pos = steps(source + step + 1,
                        step + 1, dest);
 
        // if we go on negative side
        int neg = steps(source - step - 1,
                        step + 1, dest);
 
        // minimum of both cases
        return Math.Min(pos, neg);
    }
 
    // Driver Code
    public static void Main()
    {
        int dest = 11;
        Console.WriteLine("No. of steps required"+
                             " to reach " + dest +
                      " is " + steps(0, 0, dest));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to count number
// of steps to reach a point
 
// Function to count number
// of steps required to reach
// a destination
 
// source -> source vertex
// step -> value of last step taken
// dest -> destination vertex
function steps($source, $step, $dest)
{
    // base cases
    if (abs($source) > ($dest))
        return PHP_INT_MAX;
    if ($source == $dest)
        return $step;
 
    // at each point we
    // can go either way
 
    // if we go on positive side
    $pos = steps($source + $step + 1,
                   $step + 1, $dest);
 
    // if we go on negative side
    $neg = steps($source - $step - 1,
                   $step + 1, $dest);
 
    // minimum of both cases
    return min($pos, $neg);
}
 
// Driver code
$dest = 11;
echo "No. of steps required to reach ",
     $dest, " is ", steps(0, 0, $dest);
 
// This code is contributed by aj_36
?>

<script>
// JavaScript program to count number of
// steps to reach a point
 
// Function to count number of steps
// required to reach a destination
 
// source -> source vertex
// step -> value of last step taken
// dest -> destination vertex
function steps(source, step, dest)
{
 
    // base cases
    if (Math.abs(source) > (dest))
        return Number.MAX_SAFE_INTEGER;
    if (source == dest) return step;
 
    // at each point we can go either way
    // if we go on positive side
    let pos = steps(source + step + 1,
                    step + 1, dest);
 
    // if we go on negative side
    let neg = steps(source - step - 1,
                    step + 1, dest);
 
    // minimum of both cases
    return Math.min(pos, neg);
}
 
// Driver code
    let dest = 11;
    document.write("No. of steps required to reach "
                            + dest + " is "
                        + steps(0, 0, dest));
 
// This code is contributed by Surbhi Tyagi.
</script>

No. of steps required to reach 11 is 5

Gracias a Arpit Thapar por proporcionar el algoritmo y la implementación anteriores. 

Solución optimizada: encuentre movimientos mínimos para alcanzar el objetivo en una línea infinita

Este artículo es una contribución de Abhay. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.