Minimum Number of Jumps-Asked in Adobe

Problem Statement :

Given an array of N integers arr[] where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.

Note: Return -1 if you can’t reach the end of the array.

Input Format:

The input contains two lines.

The first line contains the value of N, denoting the number of elements in the array.

The second line contains the array arr[], having ’N’ elements.

Output Format:

The output contains one line containing the number of jumps required.

Explanation of Test case:

Approach:

  1. if n <= 1, then return 0, because that is the destination
  2. If arr[0] == 0 then return -1 as answer (no jumps are possible)
  3. Now, Initialize maxrange and steps with arr[0], and jumps with 1 (as 1 jump will be required)
  4. Now, starting iteration from index 1, the above values are updated as follows:

First, we test whether we have reached the end of the array, in that case, we just need to return the jump variable
if (i == arr.length — 1) return jump;

Next, we update the maxrange. This is equal to the maximum of maxrange and i+arr[i](the number of steps we can take from the current position).
maxrange = max(maxrange,i+arr[i]);

We used up a step to get to the current index, so steps has to be decreased.
step — ;

If no more steps are remaining (i.e. steps=0, then we must have used a jump. Therefore increase jump. Since we know that it is possible to reach maxrange, we again initialize the steps to the number of steps to reach maxReach from position i. But before re-initializing step, we also check whether a step is becoming zero or negative. In this case, It is not possible to reach further.

5. Print the returned value

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!