# Minimum Jumps

#### Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

#### ‘Arcade’ is a very famous mall in Berland. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in any shop between (i) to (i + Arr[i]), where Arr[i] is a constant given for each shop.

#### 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.
```

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’.

In the previous approach, we are recalculating the answer to reach the last shop from a shop. We can optimise it by storing the answer for the amount which we have calculated.

For example, if the given array is {2, 1, 3, 2, 4}:

We are recalculating the answer for shops {2, 3}.

So since there are overlapping solutions, we can store the solution which we have calculated. For this, we will make an array DP to store the answer.

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

**Algorithm:**

- In a recursive state, if we know the answer for the ith shop, then we will directly return the answer.

- Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.
- Make an array DP of size N, initialize it with -1.
- Call the function: minimumJumpsHelper(i).
- If i is equal to N, return 0.
- If DP[i] is not equal to -1, return DP[i]
- 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).
- Update DP[i], DP[i] = ans.
- Return the ‘ans’.

Make an array DP of size N to store the answer.

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

- DP[N - 1] = 0.
- Initialize all other values with a maximum value (INT_MAX).
- Now iterate on shops from N - 2 to 1
- Let ‘i’ denote the current shop.
- Iterate on the shops where we can jump from the ith shop, i.e., from (i + 1) to (i + Arr[i]).
- Update DP[i], DP[i] = min(DP[i] , 1 + DP[j]) (where j denotes the shop, where we jumped).

- Return DP[0] as the answer.

In this approach, we will calculate the farthest shop we can reach from shop 0 with x number of jumps.

For example, if the given array is {2, 3, 1, 2, 1} :

For x=1, we can reach shop 2 (shop 0 -> shop2).

For x=2, we can reach shop 4 (shop 0 -> shop1 -> shop 4)

Hence, we require a minimum two jumps to reach the last shop.

**Algorithm:**

- Make three variables ‘maxReach’, ‘jumpsTaken’, and ‘stepsLeft’.
**‘jumpsTaken’**denotes the number of jumps taken.**‘maxReach’**denotes the farthest shop we can reach with ‘jumpsTaken’ number of jumps.**‘stepsLeft’**denotes the number of steps we can still take (1 step means moving from shop i to shop (i + 1)).

- Initialise variables:
- jumpsTaken = 1
- maxReach = Arr[0]
- stepsLeft = Arr[0]

- Iterate on the shops from shop 1 to N - 2, let
**i**denote the current shop.- Update ‘maxReach’, maxReach = max(maxReach, i + Arr[i]).
- Decrement ‘stepsLeft’ by 1, stepsLeft = stepsLeft - 1.
- If stepsLeft is equal to 0:
- Increment ‘jumpsTaken’ by 1, jumpsTaken = jumpsTaken + 1.
- If i is greater than or equal to ‘maxReach’, then we cannot jump from shop i to any other shop, so we will return -1.
- Else, stepsLeft = maxReach - i.

- Return ‘jumpsTaken’.