FastPrep

Description

Solutions

Submission

Count Triplets

🔥 FULLTIME

Given an array of n distinct integers, d = [d[0], d[1], ..., d[n-1]], and an integer threshold, t, how many (a, b, c) index triplets exist that satisfy both of the following conditions?

d[a] < d[b] < d[c]
d[a] + d[b] + d[c] ≤ t

Function Description

Complete the function triplets in the editor.

triplets has the following parameter(s):

1. int t: an integer threshold
2. int d[n]: an array of integers

Returns

long integer: a long integer that denotes the number of (a, b, c) triplets that satisfy the given conditions

Example 1:

Input:  t = 8, d = [1, 2, 3, 4, 5]
Output: 4 
Explanation:
The following 4 triplets satisfy the constraints:
      
        (1,2,3) → 1 + 2 + 3 = 6 ≤ 8
        (1,2,4) → 1 + 2 + 4 = 7 ≤ 8
        (1,2,5) → 1 + 2 + 5 = 8 ≤ 8
        (1,3,4) → 1 + 3 + 4 = 8 ≤ 8

Example 2:

Input:  t = 8, d = [1, 2, 3, 4, 6]
Output: 3 
Explanation:
Given t = 8 and d = [1, 2, 3, 4, 6], the following triplets satisfy the conditions:
     
(0, 1, 2) → 1 + 2 + 3 ≤ 8
(0, 1, 3) → 1 + 2 + 4 ≤ 8
(0, 2, 3) → 1 + 3 + 4 ≤ 8

Constraints:

0 ≤ d[i] ≤ 10⁹
0 < t < 3 × 10⁹