 0

Smaller Than Triplet Sum

Difficulty: MEDIUM
Avg. time to solve
40 min
Success Rate
60%

Problem Statement

You task is to find the count of triplets i, j, k ( 0 ≤ i < j < k < N ), such that 'ARR[i]' + 'ARR[j]' + 'ARR[j]' is less than the value of ‘TARGET’.

For Example :
If ‘N’ = 7, ‘ARR’ = { 1, 5, 2, 3, 4, 6, 7 } and ‘TARGET’ = 9

Then, there are three triplets with sum less than 9:
1) {1, 5, 2}
2) {1, 2, 3}
3) {1, 2, 4}
4) {1, 3, 4}

Thus, the output will be 4.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

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

The second line of each test case contains 'N' integers ‘ARR’, denoting the array elements.

The third line of each test case contains a single integer ‘TARGET’, denoting the target value to evaluate the smaller sum.
Output Format :
For each test case, print the count of triplets having a sum less than the given target value.

Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ 'T' ≤ 10
1 ≤ 'N' ≤ 100
-100 ≤ 'ARR[i]' ≤ 100
-100 ≤ 'TARGET' ≤ 100

Time Limit: 1 sec
2
7
1 5 2 3 4 6 7
9
6
-1 0 2 3 4 6
4
4
3
Explanation For Sample Input 1 :
For test case 1 :
We will print 4 because:
The following four triplets have sum less than 9: {1, 5, 2}, {1, 2, 3}, {1, 2, 4} and {1, 3, 4}.

For test case 2 :
We will print 3 because:
The following three triplets have sum less than 4: {-1, 0, 2}, {-1, 0, 3} and {-1, 0, 4}.
2
4
3 1 2 0
100
3
1 1 0
2
Sample Output 2 :
4
0   Console