Problem Statement :
Given an array of N integers arr[] where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.
Note: Return -1 if you can’t reach the end of the array.
Input Format:
The input contains two lines.
The first line contains the value of N, denoting the number of elements in the array.
The second line contains the array arr[], having ’N’ elements.
Output Format:
The output contains one line containing the number of jumps required.
Explanation of Test case:
First jump from 1st element to 2nd
element with value 3. Now, from here
we jump to 5th element with value 9,
and from here we will jump to last.Approach:
- if n <= 1, then return 0, because that is the destination
- If arr[0] == 0 then return -1 as answer (no jumps are possible)
- Now, Initialize maxrange and steps with arr[0], and jumps with 1 (as 1 jump will be required)
- Now, starting iteration from index 1, the above values are updated as follows:
First, we test whether we have reached the end of the array, in that case, we just need to return the jump variable
if (i == arr.length — 1) return jump;
Next, we update the maxrange. This is equal to the maximum of maxrange and i+arr[i](the number of steps we can take from the current position).
maxrange = max(maxrange,i+arr[i]);
We used up a step to get to the current index, so steps has to be decreased.
step — ;
If no more steps are remaining (i.e. steps=0, then we must have used a jump. Therefore increase jump. Since we know that it is possible to reach maxrange, we again initialize the steps to the number of steps to reach maxReach from position i. But before re-initializing step, we also check whether a step is becoming zero or negative. In this case, It is not possible to reach further.
if (step == 0)
{
jump++; if(i>=maxReach) return -1; step = maxReach — i;
}
5. Print the returned value
