# Minimum Jumps

Posted: 3 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### There are N shops in the mall, numbered from 0 to N-1. Bob's wife starts her shopping journey from shop 0 and ends it in shop N-1. As the mall is very crowded on Fridays, unfortunately, Bob gets lost from his wife. So he wants to know, what is the minimum number of trampoline jumps from shop 0 he has to make in order to reach shop N-1 and see his wife again. If it is impossible to reach the last shop, return -1.

##### Input format :
``````The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow.

The first line of each test case contains a positive integer N, which represents the number of shops.

The next line contains 'N' single space-separated positive integers representing a constant given for each shop.
``````
##### Output Format :
``````For each test case, print the minimum number of jumps or -1, if it is impossible to reach the last shop.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= Arr[i] <= N
Where T is the number of test cases, N is the size of the array and Arr[i] is the ith element in the array.
``````
Approach 1

We will recursively find the minimum number of jumps.

Algorithm:

Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.

• Call the function: minimumJumpsHelper(i).
• If i is equal to N-1, return 0.
• Make a variable ‘ans’ that stores the minimum number of jumps needed to reach the last shop from the current shop.
• Initialize ‘ans’ with a maximum value (INT_MAX).
• Iterate on the shops from (i + 1) to (i + Arr[i]) and update the answer, i.e., ans = min( ans, 1 + minimumJumpsHelper(j) ) (where j denotes the shop, where we jumped).
• Return the ‘ans’.