Watch 3 video solutions for Number of Divisible Triplet Sums, a medium level problem involving Array, Hash Table. This walkthrough by Programming Live with Larry has 2,024 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
nums and an integer d, return the number of triplets (i, j, k) such that i < j < k and (nums[i] + nums[j] + nums[k]) % d == 0.
Example 1:
Input: nums = [3,3,4,7,8], d = 5 Output: 3 Explanation: The triplets which are divisible by 5 are: (0, 1, 2), (0, 2, 4), (1, 2, 4). It can be shown that no other triplet is divisible by 5. Hence, the answer is 3.
Example 2:
Input: nums = [3,3,3,3], d = 3 Output: 4 Explanation: Any triplet chosen here has a sum of 9, which is divisible by 3. Hence, the answer is the total number of triplets which is 4.
Example 3:
Input: nums = [3,3,3,3], d = 6 Output: 0 Explanation: Any triplet chosen here has a sum of 9, which is not divisible by 6. Hence, the answer is 0.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1091 <= d <= 109Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(1) | Useful for understanding the constraint i < j < k or when input size is extremely small |
| Hash Table + Enumeration | O(n^2) | O(d) | General optimal approach using remainder counting and constant-time hash lookups |