Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

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

Published on 11 Mar 2020

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


C++
Python 3

Output
2,3,1,1,4
2


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


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises