Program to find minimum number of jumps to reach end of an array

Program to find minimum number of jumps to reach end of an array is discussed here. 

DESCRIPTION:

You are at the start of an array. (in 0). Every index will hold the value of maximum steps you take from that index(if the value is 0 then the person cannot move) in one jump. You have to reach the end of the array. Print the minimum number of steps required to reach the endpoint. If it is not possible to reach the end, print -1.

For example,

Sample Input: 

10 (Number of elements of the array)
5 5 0 4 1 4 5 5 3 2  (Steps taken at each jump)

Sample Output:

2

Explanation:

The first element is 5. Using that, we can reach 5 steps. So, reach the 5th index, which is 4. From there, we can make 4 steps, which leads us to the end of the array.

start -> 5 -> 4 -> end

  1. Input the number of elements of the array.
  2. Input the elements of the array (At most steps at each step).
  3. Assign max_level = arr[0], step = arr[0] and jump = 1.
  4. if(arr[0] == ) 
  5.                     jump = -1
  6. else
  7.                 Repeat from i  = 1 to n – 1    
  8.                      maxLevel = max(maxLevel,i+a[i]);
  9.                      step–;
  10.                      if(step == 0)
  11.                           jump++;
  12.                      if(i>= maxLevel)
  13.                          jump=-1;
  14.                          break;
  15.                    step=maxLevel-i;
  16.    Return jump.

Program to find the minimum number of jumps to reach the end of an array is given below.

/* C++ program to find the minimum number of jumps to reach the end of an array */

include<iostream>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
       cin>>a[i];
   int maxLevel = a[0];
   int step=a[0];
   int jump=1;
   if(a[0] == 0)
       jump=-1;
   else
       for(int i=1;i<n-1;i++)
       {
           maxLevel = max(maxLevel,i+a[i]);
           step–;
           if(step == 0)
           {
               jump++;
               if(i>= maxLevel)
               {
                   jump=-1;
                   break;
               }
               step=maxLevel-i;
           }
       }
   cout<<jump;    
}

Test Case 1

I/P
10
2 2 9 4 9 1 2 3 4 5
O/P
2

Test Case 2

I/P
20
1 4 5 1 2 5 1 2 3 2 3 3 2 5 0 5 3 1 3 0
O/P
6

Test Case 3

I/P
10
5 5 0 4 1 4 5 5 3 2
O/P
2

Test Case 4

I/P
10
5 5 0 2 2 0 1 0 3 2
O/P
-1

Test Case 5

I/P
5
0 1 2  3 5
O/P
-1