Minimum number of steps to reach at the end in C++

In this tutorial, we will learn how to get the minimum number of steps to reach at the end. In the first place, we will have an integer array where each element represents the maximum number of steps that one can move forward.

  • For Example:
  • Given arr[ ] = { 1, 2, 2, 3, 2, 4, 5, 8, 9, 2}
  • Here, the first element can move up to the second element.
  • But then, the 2nd element can take up to two moves.
  • The 2nd element can jump to the 3rd element as well as the 2nd element according to the minimum number of steps that will be taken further.
  • Minimum steps: 4
  • Sequence: 1->2->3->4->2

 

NOTE: If an element is zero, then we cannot move forward through that element.
Recursive Approach:

  • We will start from the first element and recur for all the elements which are reachable from the current position.
  • A base case is set in the recursive approach ie. when the source and destination are the same.

You may also like:
How to swap two numbers without using the third variable in C++

 

Minimum number of steps to reach at the end

Here is the implemented code:

// C++ program to get Minimum number of jumps to reach at the end 
#include<iostream>
#include <bits/stdc++.h> 
using namespace std; 

// recursive function to get minimum number of steps to reach at the end 
int minssteps(int arr[], int s, int d) 
{ 
  
// Base case: 
if (d == s) 
  return 0; 


if (arr[s] == 0) 
  return INT_MAX; 

// Traverse through all the points 
// reachable source.here, source changes everytime. Recursively 
// get the minimum number of jumps 
// needed to reach destination from these 
// reachable sources. 
int min = INT_MAX; 
for (int i = l + 1; i <= h && 
    i <= l + arr[l]; i++) 
{ 
  int steps = minsteps(arr, i, h); 
  if(steps != INT_MAX && steps + 1 < min) 
    min = steps + 1; 
} 

return min; 
} 

int main() 
{ 
  int a[] = {1, 2, 2, 3, 2, 
        4, 5, 8, 9, 2}; 
  int n = sizeof(a)/sizeof(a[0]); 
  cout << "Minimum number of steps to reach at the end is "
    << minJumps(a, 0, n-1); 
  return 0; 
} 

 

Output Explanation:

OUTPUT: Minimum number of steps to reach at the end is 4

Leave a Reply

Your email address will not be published.