Smaller Than Triplet Sum

Posted: 1 Dec, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array ‘ARR’ containing ‘N’ integers, and you are also given an integer ‘TARGET’.

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
Approach 1

We can simply run three loops and generate all the possible triplets, for each triplet we can then check if its sum is less than the given target value, we can finally return the count of triplets that had a sum less than the target value (Standard Brute Force Approach!).

 

The steps are as follows :

  1. Initialize a variable ‘count’ equal to 0, this will store the count of valid triplets.
  2. Run the outermost FOR loop for variable ‘i’ from 0 to ‘N’ - 1, run the middle FOR loop for variable ‘j’ from ‘i’ + 1 to ‘N’ - 1 and run the innermost loop FOR loop for variable ‘k’ from ‘j’ + 1 to ‘N’ - 1:
    • For the triplet ARR[i], ARR[j], ARR[k], calculate its sum, and if it is less than ‘TARGET’ then increment the value of ‘count’ to include the generated triplet in answer.
  3. Finally, return the value of ‘count’.
Try Problem