NINJA'S JUMP

Hard
0/120
Average time to solve is 15m
profile
Contributed by
20 upvotes
Asked in companies
Morgan StanleyAmazonExpedia Group

Problem statement

Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.

So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.

For jumping you have to follow below instructions:

You may jump forward from index ‘i’ to index ‘j’ (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index ‘j’ such that ‘arr[i] <= arr[j]’ and ‘arr[j]’ is the smallest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index j.

During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index ‘j’ such that ‘arr[i] >= arr[j]’ and ‘arr[j]’ is the largest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index ‘j’.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5
20 23 22 24 25
5
5 6 4 4 7

Sample Output 1:

2
3

Explanation for sample input 1:

Test Case 1:
For the first test case, if we start from index i = 0, we can make our first jump to i = 2, since it is smaller than all other array values but then we cannot jump anymore. 
If we start from the index i = 1, or i = 2 we can make the first jump to i = 3 then we cannot jump anymore.
If we start from index i = 3 we have to make only one jump and we reach the end.
And if we start from index i = 4 we are already at the end.
So we return ‘2’ as our answer as there are ‘2’ good starting index.

Test Case 2:
For the test case if we start From starting index i = 0, we make jumps to i = 1, i = 2, i = 3
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.

In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some number of jumps so we return ‘3’ as our answer.

Sample Input 2:

1
5
5 1 3 4 2

Sample Output 2:

3

Explanation of sample input 2:

As we can reach the end by starting from index 1, 2, 4
Hint

Can you traverse the whole array for each index?

Approaches (3)
BRUTE APPROACH

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.
Time Complexity

O(N ^ 2), where ‘N’ represents the size of the given array.

 

As for each index, we are traversing the whole array so we have to run two nested loops which make the complexity O(N ^ 2).

Space Complexity

O(1).

 

As no extra space is required.

Code Solution
(100% EXP penalty)
NINJA'S JUMP
Full screen
Console