Number of Divisible Triplet Sums
Asked at Visa
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²).
Asked At
| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Only remainders modulo d matter.
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.
Scan j from left to right. Before processing j, the map holds remainders of indices 0..j-1. After processing, add nums[j] % d.
Each (j, k) pair is an O(1) lookup, so the total is O(n²) — about 10^6 operations for n = 1000.
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)).
What Trips People Up in Real Interviews
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.
Solution Code
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 resFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.