Frog Jump Problem

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.

Solution

Leave a Reply

Your email address will not be published. Required fields are marked *