MediumArrayHash TableUpdated Sep 2026

2964. Number of Divisible Triplet Sums

Asked at Visa

Difficulty

Medium

Time

O(n^2)

Space

O(min(n, d))

Pattern

Array

Companies

1

Problem

You are given an integer array nums and an integer d. Count how many triplets of indices (i, j, k) satisfy two things at once: the indices are in increasing order (i < j < k), and the sum nums[i] + nums[j] + nums[k] is divisible by d.

Return that count as an integer. Two triplets are different if they use different index positions, even when the values at those positions are equal.

A brute-force check of every triple costs O(n³), which is too slow for n = 1000. The trick is that only remainders modulo d matter for divisibility, so you can fix the middle index j and count matching earlier elements with a hash map.

Pick three indices in order

nums3347801234ijkOne valid triplet: indices 0, 1, 2 with sum 3 + 3 + 4= 10nums3347801234ijkAnother valid triplet: indices 0, 2, 4 with sum 3 + 4+ 8 = 15
We need i < j < k and a sum that is a multiple of d; here (0,1,2) gives 3+3+4 = 10, which is divisible by 5.

Constraints

  • ●1 <= nums.length <= 1000
  • ●1 <= nums[i] <= 10^9
  • ●1 <= d <= 10^9

Examples

Example 1
Inputnums = [3,3,4,7,8], d = 5
Output3
WhyThe sums 3+3+4=10, 3+4+8=15 and 3+4+8=15 are all divisible by 5. These come from index triples (0,1,2), (0,2,4) and (1,2,4). No other triple works, so the answer is 3.
Example 2
Inputnums = [3,3,3,3], d = 3
Output4
WhyEvery triple sums to 9, and 9 % 3 == 0. There are C(4,3) = 4 ways to choose 3 indices out of 4, so all 4 triples count.
Example 3
Inputnums = [3,3,3,3], d = 6
Output0
WhyEvery triple still sums to 9, but 9 % 6 == 3, which is not 0. So none of the triples is divisible by 6.

Asked At

1 companies
CompanyDifficulty
VisaMediumView all Visa questions →

How to Think About It

1

Only remainders modulo d matter.

2

Key insight: fix j (the middle index). For each k > j, the first element must have remainder (-(nums[j] + nums[k])) mod d. Count how many i < j have that remainder with a hash map.

3

Scan j from left to right. Before processing j, the map holds remainders of indices 0..j-1. After processing, add nums[j] % d.

4

Each (j, k) pair is an O(1) lookup, so the total is O(n²) — about 10^6 operations for n = 1000.

5

Walkthrough: nums = [3,3,4,7,8], d = 5: valid triples are (0,1,2), (0,2,4), (1,2,4) -> 3.

Optimal Approach

Step 1: count = {} (remainder -> how many earlier indices), res = 0.
Step 2: For each j:
For each k > j: need = (-(nums[j] + nums[k])) % d; res += count.get(need, 0).
count[nums[j] % d] += 1.
Step 3: Return res.

Time: O(n²). Space: O(min(n, d)).

Fix the middle index j

numsmap: {3: 1}3347801234jkj = 1, k = 2: need = (-(3 + 4)) mod 5 = 3, and the maphas one earlier 3, so we add 1numsmap: {3: 2}3347801234jkj = 2, k = 4: need = (-(4 + 8)) mod 5 = 3, and the mapnow has two earlier 3s, so we add 2need = (-(nums[j] + nums[k])) mod dres += count[need]then count[nums[j] mod d] += 1
For each j we look at every k to its right, and ask the map how many earlier elements have the remainder that completes the sum.
ComplexityTime O(n^2)Space O(min(n, d))The cost comes from the double loop over the middle index j and the right index k, while the hash map stores at most one entry per distinct remainder.

What Trips People Up in Real Interviews

1

Triple nested loops — O(n³) is 10^9 for n = 1000.

2

Negative remainders in C++/Java: normalize with ((x % d) + d) % d.

3

Adding nums[j] to the map before counting pairs for j, which lets i == j.

4

Overflow when adding values up to 10^9 in 32-bit integers — reduce modulo d first.

Solution Code

O(n^2) time
def divisibleTripletCount(nums, d):
    count = {}
    res = 0
    n = len(nums)
    for j in range(n):
        for k in range(j + 1, n):
            need = (-(nums[j] + nums[k])) % d
            res += count.get(need, 0)
        r = nums[j] % d
        count[r] = count.get(r, 0) + 1
    return res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Divisible Triplet Sums problem?

Number of Divisible Triplet Sums asks how many index triples `i < j < k` have `nums[i] + nums[j] + nums[k]` divisible by `d`. Checking all triples is `O(n³)`; fixing the middle index and counting remainders on the left brings it down to `O(n²)`.

How do you solve Number of Divisible Triplet Sums?

The optimal approach runs in O(n^2) time and O(min(n, d)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Divisible Triplet Sums?

Number of Divisible Triplet Sums is asked at Visa. It is a medium difficulty problem.

What are common mistakes on Number of Divisible Triplet Sums?
  • Triple nested loops — `O(n³)` is `10^9` for `n = 1000`.
  • Negative remainders in C++/Java: normalize with `((x % d) + d) % d`.
  • Adding `nums[j]` to the map before counting pairs for `j`, which lets `i == j`.
  • Overflow when adding values up to `10^9` in 32-bit integers — reduce modulo `d` first.