Problem title
Avg time to solve

Square Root
15 mins
Merge Two Sorted Linked Lists
15 mins
Longest Consecutive Sequence
40 mins
Time To Burn Tree
50 mins
Overlapping ABBA
10 mins
Minimum Jumps
25 mins
Best Time to Buy and Sell Stock
20 mins
Rod cutting problem
40 mins
Merge Two Sorted Arrays
15 mins
Majority element
15 mins

Minimum Jumps

Difficulty: MEDIUM
Contributed By
Shivam |Level 1
Avg. time to solve
25 min
Success Rate

Problem Statement

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.
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.
Sample Input 1:
2 1 3 2 4
3 2 1
Sample Output 1:
Explanation For Sample Input 1:
In the 1st test case, Bobs jumps from shop 0 to shop 2 and then jumps from shop 2 to shop 4, so he needs two jumps to reach the last shop.

In the 2nd test case, Bobs jumps from shop 0 to shop 2, so he needs only one jump to reach the last shop.
Sample Input 2:
1 0 3 2 1
1 1 1 1
Sample Output 2:
Reset Code
Full screen