FastPrep
Problem · Sorting

Count Increasing Triplets

Learn this problem
● MediumCitadel logoCitadelFULLTIMEOA

Problem statement

Given an array d of distinct integers and a threshold t, count the triplets of distinct indices (a, b, c) that satisfy both conditions:

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

Because all values in d are distinct, each selection of three values has at most one ordering that is strictly increasing.

Return the number of valid triplets as a long.

Function

triplets(t: long, d: int[]) → long

Examples

Example 1

t = 8d = [1, 2, 3, 4, 5]return = 4

The valid increasing value triplets are:

  • (1, 2, 3), with sum 6.
  • (1, 2, 4), with sum 7.
  • (1, 2, 5), with sum 8.
  • (1, 3, 4), with sum 8.

Therefore the result is 4.

Example 2

t = 8d = [1, 2, 3, 4, 6]return = 3

The valid increasing value triplets are (1, 2, 3), (1, 2, 4), and (1, 3, 4). Their sums are at most 8, so the result is 3.

Constraints

  • All values in d are distinct.
  • 0 ≤ d[i] ≤ 10^9
  • 0 < t < 3 × 10^9

More Citadel problems

drafts saved locally
public long triplets(long t, int[] d) {
    // Write your code here
}
t8
d[1, 2, 3, 4, 5]
expected4
checking account