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:

First jump from 1st element to 2nd 
element with value 3. Now, from here
we jump to 5th element with value 9,
and from here we will jump to last.

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.

if (step == 0)
{
jump++;
if(i>=maxReach) return -1; step = maxReach — i;
}

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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Would you like some Tries with that?

Case Study on Ansible !

NVDA and Firefox 58 — The team is regaining strength

.Net Core 3.1 Microservice Api Gateway Ocelot Library

Beginners guide to Docker

Being A S.O.L.I.D. Engineer

Upskilling on Azure AD B2C-Localisation

Detailed explanation and examples of the suspension, recovery, and exit of python threads

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!

More from Medium

One Mile on the globe Puzzle

Schrödinger (D.E. Shaw) Interview Experience (On-Campus)

My Interview Experiences (Part-1)

One interview, Many learnings