Subarrays with length solution codechef

Subarrays with length solution codechef

You are given an array AA of length NN.

Determine the count of subarrays of AA which contain their length as an element.

Formally, count the number of pairs (L,R)(L,R) (1LRN)(1≤L≤R≤N) such that: (RL+1){AL,AL+1,,AR}(R−L+1)∈{AL,AL+1,…,AR}.

• Discover & apply to 20M+ jobs/internships on LinkedIn
• Reach out to hiring managers/recruiters/mentors directly
• Find career paths that people similar to them have taken
• Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

Input Format

• First line will contain TT, number of test cases. Then the test cases follow.
• First line of each test case contains an integer NN denoting the length of the array AA.
• Second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN – denoting the array AA.

Output Format

For each test case, output the count of subarrays containing their lengths.

Subarrays with length solution codechef

• 1T10001≤T≤1000
• 1N21051≤N≤2⋅105
• 1AiN1≤Ai≤N
• Sum of NN over all test cases does not exceed 51055⋅105.

Sample Input 1

3
3
1 2 1
5
2 3 1 3 5
10
10 7 4 4 2 9 2 1 9 3


Sample Output 1

4
6
15


Subarrays with length solution codechef

Test Case 11: There are 44 subarrays (i,j)(i,j) containing their lengths. They are (1,1),(1,2),(2,3),(1,1),(1,2),(2,3), and (3,3)(3,3).

Test Case 22: There are 66 subarrays (i,j)(i,j) containing their lengths. They are (1,2),(1,3),(1,5),(2,4),(3,3),(1,2),(1,3),(1,5),(2,4),(3,3), and (3,5)(3,5).