Find minimum number of jumps to reach end in Python

In this tutorial, we will learn how to write a program in Python for finding the minimum number of jumps to reach the end of an array. We will give a set of numbers separated by a single space. So that the program can convert it into a list.

Minimum number of jumps to reach the end in Python:

We will give a set of numbers separated by a space and make it as an array or list. Condition in the program is that you can jump a maximum number of jumps form index i is l[i]. Where l is our input. For example, let us take an example l = [2,3,1,4,6,1]. You can either jump 0,1,2 or 3  indices from index 1 ( l[1] ) ahead.

The minimum number of jumps to reach the end: Process

Step:1   Initialize end, farthest, jumps with zero. As we go into the process you will understand the terms and why we use them.

Step:2  Initialize zeroth index with i.

Step:3   Find the maximum index that you can jump from the current index using max() function. And assign the value to farthest.

farthest = max(farthest,i+l[i])

 

Step:4  Jump to maximum indices from the current index.

Step:5  When i and end are equal, Assign farthest to end. (Here, the word “end” is nothing but a maximum index that you can reach. When “i” reach “end” value, we have to increment the value of the jumps by 1.)

Step:6   Go to step 3 until you reach the but one last value of the array.

Also read: Barrier Objects in Python with Example

l = input().split(" ")
l=[int(i) for i in l]
end = 0
jumps = 0
farthest = 0
for i in range(len(l)-1):
    farthest = max(farthest,i+l[i])
    if(i==end):
        jumps+= 1
        end = farthest
        
print(jumps)
Sample input: 2 3 1 4 6 1
Ouput: 3

Leave a Reply