Number of Divisible Triplet Sums

Number of Divisible Triplet Sums

What is this problem about?

The Number of Divisible Triplet Sums problem asks you to count triplets (i, j, k) where i < j < k and arr[i] + arr[j] + arr[k] is divisible by a given d. This coding problem uses a hash map of remainder frequencies to count valid triplets efficiently in O(n²) rather than O(n³).

Why is this asked in interviews?

Activision, LinkedIn, ZScaler, and Palantir ask this to test the two-sum frequency extension to triplets. By fixing j, iterating k from j+1 to n-1 and building a remainder map of arr[i] values (i < j), you can count how many i values make the triplet sum divisible. The array and hash table interview pattern is directly applied.

Algorithmic pattern used

Fix middle element + prefix remainder map. For each j: after processing all j positions, maintain a hash map count[remainder] for all arr[i] where i < j. For each k > j: compute the needed remainder for arr[i]: needed = (-arr[j] - arr[k]) % d. Look up count[needed]. Add this to the result. After each j iteration, add arr[j] % d to the map.

Example explanation

arr=[3,3,4,7,8], d=5. Fix j=2 (arr[j]=4). Map of arr[i] %5 for i<2: {3%5:2} = {3:2}. For each k>2: k=3 (arr[k]=7), needed=(-(4+7)%5+5)%5=(5-11%5)%5=(5-1)%5=4≠3, no match. k=4 (arr[k]=8), needed=(-(4+8)%5+5)%5=(5-7%5)%5=(5-2)%5=3, match! count[3]=2. Add 2. Continue for all j. Sum all contributions.

Common mistakes candidates make

• O(n³) brute force (check all triplets).
• Incorrect modulo for negative numbers (use ((-x) % d + d) % d in languages with negative modulo).
• Building the map lazily — the map for j should only contain i < j, not i ≤ j.
• Counting pairs (i,k) as triplets or missing the j<k ordering.

Interview preparation tip

Triplet sum divisibility extends the "two sum with modular arithmetic" pattern. For two-sum modular: fix one element, use a hash map for the complement. For triplet: fix the middle element, keep a prefix map for the left element, scan right for the right element. The modular complement formula: needed = (-a - b) % d (use ((-a-b)%d+d)%d for safety). Practice the two-sum modular pattern first, then apply the same idea to three elements.