Consider 0 based indexing.
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ denoting the number of elements in the given sequence.
The second line of each test case contains ‘N’ space-separated integers denoting the elements in the sequence.
For each test case, print a single line containing a single integer denoting the minimum number of jumps required to reach the last index.
The output of each test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 50
1 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 4
Where ‘ARR[i]’ denotes the ‘i-th’ element of the ‘ARR’.
Time limit: 1 sec.
Keeping the above example in mind, we can write the following Recursive solution:
Keeping in mind the above idea, we can use the following approach:
Now, think about the following,
To reach the last index we try to reach the minimum index from which we can reach the last index.
-- Now what is the minimum index from which we can reach the last index in one jump?
From -- index 0 we can at max go 0 + 5 = 5, not 11
From -- index 1, we can at max go 1 + 9 = 10, not 11
From -- index 2, we can at max go 2 + 3 = 5, not 11
From -- index 3,we can at max go 3 + 2 = 5,not 11
From -- index 4 we can at max go, 4 + 1 = 5, not 11
From -- index 5, we can at max go 5 + 0 = 5, not 11
From -- index 6, we can at max go 6 + 2 = 8, not 11
From -- index 7, we can at max go 7 + 3 = 10, not 11
From -- index 8, we can at max go 8 + 3 = 11, yes!
Thus we have to first reach index 8.
-- Now what is the minimum index from which we can reach index 8 in one jump?
-- index 0,we can at max go 0 + 5 = 5, no
-- index 1, we can at max go 1 + 9 = 10, yes
Thus we have to first reach index 1.
-- Now what is the minimum index from which we can reach index 1 in one jump?
-- index 0,we can at max go 0 + 5 = 5, yes
Therefore, 3 jumps in total.
Keeping in mind the above example, we can use the following approach:
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Maximize
Negative To The End
8-Queen Problem