FastPrepCounting Triplets Divisible by D

Counting Triplets Divisible by D

AT&T logoAT&T● MediumNEW GRADOA
Learn

Problem statement

Given an integer array arr and a positive integer d, count the index triplets (i, j, k) such that 0 <= i < j < k < arr.length and (arr[i] + arr[j] + arr[k]) is divisible by d.

Return the number of valid triplets as a 64-bit integer.

Function

countTriplets(arr: int[], d: int) → long

Examples

Example 1

arr = [3,3,4,7,8]d = 5return = 3

The valid one-based index triplets are (1,2,3), (1,3,5), and (2,3,5). Their sums are 10, 15, and 15.

Example 2

arr = [1,2,3,4]d = 3return = 2

The triplets using values (1,2,3) and (2,3,4) have sums 6 and 9, both divisible by 3.

Example 3

arr = [-1,0,1,2]d = 2return = 2

The sums -1 + 0 + 1 = 0 and -1 + 1 + 2 = 2 are divisible by 2.

Constraints

  • 3 <= arr.length <= 200000.
  • -10^9 <= arr[i] <= 10^9.
  • 1 <= d <= 2000.
  • The answer fits in a signed 64-bit integer.

More AT&T problems

See AT&T hiring insights
public long countTriplets(int[] arr, int d) {
  // write your code here
}
arr[3,3,4,7,8]
d5
expected3
Checking account…