Minimum Number of Hops to Reach the End of an Array

Each element of an array indicates the length of the hop from that particular index. For example : if A[i] is 3 then you can jump to A[i+1] or A[i+2] or A[i+3] from the ith index. The problem states that, find the minimum number of hops required to reach the end of the array. If an element is 0, then it would mean that no other element can be reached from that particular element.

Solution Approach

It can be easily solved using Dynamic Programming. I've used a recursive approach to solve the above given problem. There are a few points to keep in mind before starting with the solution.

1. We need to know when a particular path would end - A particular path would end if you can reach the last element from the current element. i.e i + A[i] >= Length of the Array.

2. We need to find the minimum of the number of hops required from all the elements that can be reached from the current element, recursively.

Solution






In the above program the input is given as 1, 2, 3, 4, 5. The output in this case would be 3. The possible paths to reach the end in the above case are :

1 -> 2 -> 3 -> 5
1 -> 2 -> 4 -> 5

In both the cases the number of hops would be 3. Therefore we would print 3 as the output.

Feel free to post your doubts below :)

Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming