Number of Divisible Triplet Sums - Solution & Explanation

Problem Overview: Given an integer array nums and an integer d, count the number of triplets (i, j, k) such that i < j < k and (nums[i] + nums[j] + nums[k]) % d == 0. The goal is to avoid checking every possible triplet while still ensuring the divisibility condition is satisfied.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct method enumerates every triplet using three nested loops. For each combination (i, j, k), compute the sum and check if it is divisible by d. This approach requires scanning all n choose 3 combinations, which leads to O(n^3) time complexity. It uses constant extra space since only counters are maintained. While inefficient for large arrays, this version clearly demonstrates the constraint i < j < k and validates the divisibility condition before optimizing.

Approach 2: Hash Table + Enumeration (O(n^2) time, O(d) space)

The optimized solution uses modular arithmetic and a frequency map. Instead of fixing all three indices, fix the middle index j and iterate k to the right. Maintain a hash table that stores the frequency of remainders nums[i] % d for all indices i < j. For each pair (j, k), compute the remainder of their sum and determine the remainder needed from i so the total becomes divisible by d. The required value is needed = (d - (nums[j] + nums[k]) % d) % d. A single hash lookup returns how many valid i indices exist.

This converts the problem from checking explicit triplets to counting compatible remainders. Each pair (j, k) performs constant-time work, producing an overall O(n^2) time complexity. The hash table stores at most d remainder buckets, so space complexity is O(d). The technique relies on properties of modular arithmetic combined with fast lookups from a hash table. Iteration across the array itself is standard array traversal.

Recommended for interviews: The hash table + enumeration approach is what interviewers typically expect. Brute force proves you understand the triplet constraint and divisibility rule, but the optimized method shows you can transform the condition using modular arithmetic and reduce the search space from cubic to quadratic time. Demonstrating the remainder transformation and constant-time hash lookups is the key insight interviewers look for.