# NINJA'S JUMP

Posted: 3 Apr, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Input Format:

``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘arr’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.
``````

#### Output Format:

``````For each test case, print a single line containing the number of starting indices, from where Ninja can reach the end by following the required jump conditions.

The output of each test case will be printed in a separate line.
``````

#### Note :

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````

#### Constraints:

``````1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6

Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘arr[i]’ represents the elements of the array.

Time Limit: 1 sec
`````` Approach 1

The idea here is to use the brute force approach and to travel the whole array for each index we will check if we can reach the last index of the array by following the given conditions.

• So we start from our first index and look for the elements which are greater than that element and we choose minimum from that.
• After choosing the minimum element now we check do we need an even-numbered count for reaching that element or an odd-numbered count for reaching the element.
• Now from that element, we check if we take the same jump the element is smaller than that or not.
• If it is not smaller then the index is not a good starting index.
• Else we repeat the above steps until we reach the end of the array.
• Now if we reach the end we increase our ‘ans’ variable by ‘1’.
• In this way, we checked for each index of our array.
• In the last, we return our ‘ans’ variable.