Smaller Than Triplet Sum

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
9 upvotes
Asked in companies
AmazonSAP LabsMTX

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
7
1 5 2 3 4 6 7
9
6
-1 0 2 3 4 6
4
Sample Output 1 :
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}.
Sample Input 2 :
2
4
3 1 2 0
100
3
1 1 0
2
Sample Output 2 :
4
0
Hint

Try to check for each possible triplet.

Approaches (3)
Brute Force

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

O( N ^ 3 ), where N denotes the size of the array.

 

We generate all the triplets, the number of triplets are of the order ~N^3, this is clearly shown by the three for loops we used to generate the triplets. 

Hence the time complexity is O( N^3 ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Smaller Than Triplet Sum
Full screen
Console