Minimum steps to reach a destination - GeeksforGeeks

Minimum steps to reach a destination - GeeksforGeeks
Given a number line from -infinity to +infinity. You start at 0 and can go either to the left or to the right. The condition is that in i'th move, you take i steps.
a) Find if you can reach a given number x
b) Find the most optimal way to reach a given number x, if we can indeed reach it. For example, 3 can be reached om 2 steps, (0, 1) (1, 3) and 4 can be reached in 3 steps (0, -1), (-1, 1) (1, 4).

The important think to note is we can reach any destination as it is always possible to make a move of length 1. At any step i, we can move forward i, then backward i+1.

1) Since distance of +5 and -5 from 0 is same, hence we find answer for absolute value of destination.

3) If at any point source vertex = destination; return number of steps.

4) Otherwise we can go in both of the possible directions. Take the minimum of steps in both cases.

From any vertex we can go to :
(current source + last step +1) and
(current source – last step -1)

5) If at any point, absolute value of our position exceeds the absolute value of our destination then it is intuitive that the shortest path is not possible from here. Hence we make the value of steps INT_MAX, so that when i take the minimum of both possibilities, this one gets eliminated.
If we don’t use this last step, the program enters into an INFINITE recursion and gives RUN TIME ERROR.

// 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);

}

http://ideone.com/OnLPt9

1. public static int minMoves(int pos, int steps, int move, int N)
2. {
3. if (Math.abs(pos) > N)
4. return Integer.MAX_VALUE;
5. if (Math.abs(pos) == N)
6. return move;
7. int j = minMoves(pos - steps, steps + 1, move + 1, N);
8. int i = minMoves(pos + steps, steps + 1, move + 1, N);
9. return Math.min(i, j);
10. }

to-do: http://ideone.com/T0wdHG
http://ideone.com/4ZHdfx
Read full article from Minimum steps to reach a destination - GeeksforGeeks