Subarray Sums Divisible by K
Asked at TikTok
Problem
Subarray Sums Divisible by K asks how many contiguous subarrays have a sum divisible by k. It is the modular cousin of Subarray Sum Equals K: two prefix sums with the same remainder bound a subarray whose sum is a multiple of k.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Brute force sums every subarray: O(n²).
Key insight: sum(i+1..j) = prefix[j] - prefix[i]. That difference is divisible by k exactly when prefix[j] % k == prefix[i] % k.
So count remainders as you go. For each new prefix remainder r, every earlier prefix with the same remainder forms a valid subarray — add count[r] to the answer, then increment count[r].
Seed count[0] = 1 for the empty prefix, so subarrays starting at index 0 are counted.
Negative numbers: in C++/Java, -1 % 5 is -1. Normalize with ((sum % k) + k) % k so equal residues compare equal.
Optimal Approach
Step 1: count = [0] * k, count[0] = 1, prefix = 0, res = 0.
Step 2: For each x:
prefix = (prefix + x) % k (normalized to be non-negative).
res += count[prefix]
count[prefix] += 1
Step 3: Return res.
Time: O(n). Space: O(k).
What Trips People Up in Real Interviews
Forgetting to normalize negative remainders in C++/Java. -2 % 5 and 3 % 5 must land in the same bucket.
Missing the count[0] = 1 seed.
Adding count[r] after incrementing it, which counts each prefix as pairing with itself.
Using a hash map when an array of size k suffices — not wrong, just slower.
Solution Code
def subarraysDivByK(nums, k):
count = [0] * k
count[0] = 1
prefix = res = 0
for x in nums:
prefix = (prefix + x) % k
res += count[prefix]
count[prefix] += 1
return resFrequently Asked Questions
What is the Subarray Sums Divisible by K problem?
Subarray Sums Divisible by K asks how many contiguous subarrays have a sum divisible by `k`. It is the modular cousin of Subarray Sum Equals K: two prefix sums with the same remainder bound a subarray whose sum is a multiple of `k`.
How do you solve Subarray Sums Divisible by K?
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 Subarray Sums Divisible by K?
Subarray Sums Divisible by K is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Subarray Sums Divisible by K?
- Forgetting to normalize negative remainders in C++/Java. `-2 % 5` and `3 % 5` must land in the same bucket.
- Missing the `count[0] = 1` seed.
- Adding `count[r]` after incrementing it, which counts each prefix as pairing with itself.
- Using a hash map when an array of size `k` suffices — not wrong, just slower.