Problem
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. Given an array of stones (non-negative integers) where each element in the array represents the maximum number of positions one can move forward from that element.
Write a program to Find the minimum number of jumps required to cross the river
Note:
1. Jump is current position + array elements
2. if array element is 0 then frog cannot move to another stone
For example:
Input arr = {2,3,0,1,3,4}
Frog can cross river in 3 jumps
Step:
- As first array element 2, frog can jump on either 3, or 0. As 0 position frog cannot move so frog will jump on index 2.
- From second array element value is 3 , frog can jump on either 0,1,3. As optimum jump frog will jump fifth array element
- From fifth array element frog can move 3 steps but as to cross river he needs only two steps
So, Frog needs 3 jumps to cross river.