MediumArrayHash TablePrefix SumUpdated Sep 2026

974. Subarray Sums Divisible by K

Asked at TikTok

Difficulty

Medium

Time

O(n)

Space

O(k)

Pattern

Array

Companies

1

Problem

You are given an integer array nums and an integer k. Count how many non-empty subarrays have a sum that is divisible by k.

A subarray is a contiguous block of the array — you take a start index and an end index and keep every element between them. Single elements count as subarrays too.

A sum is divisible by k when the remainder after dividing by k is 0. The array may contain negative numbers, so be careful with remainders.

Which blocks have a sum divisible by 5

numssum 5450-2-31012345The whole array sums to 5, which is divisible by 5, soit countsnumssum 0450-2-31012345[5,0,-2,-3] also sums to 0, another multiple of 5
Every contiguous block is a candidate; we only keep the ones whose total is a multiple of 5.

Constraints

  • ●1 <= nums.length <= 3 * 10^4
  • ●-10^4 <= nums[i] <= 10^4
  • ●2 <= k <= 10^4

Examples

Example 1
Inputnums = [4,5,0,-2,-3,1], k = 5
Output7
WhyThese seven blocks have sums 0, 5, 5, 0, 0, 0 and -5, and all of them are multiples of 5: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].
Example 2
Inputnums = [5], k = 9
Output0
WhyThe only subarray is [5], and 5 is not a multiple of 9, so the answer is 0.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Brute force sums every subarray: O(n²).

2

Key insight: sum(i+1..j) = prefix[j] - prefix[i]. That difference is divisible by k exactly when prefix[j] % k == prefix[i] % k.

3

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].

4

Seed count[0] = 1 for the empty prefix, so subarrays starting at index 0 are counted.

5

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).

Equal remainders mark valid subarrays

prefix sums04997450123456Prefix sums before each element; index 0 is the emptyprefixremainders mod 504442400123456Remainder 4 appears four times and remainder 0 twice,giving 6 + 1 = 7 pairsprefix[j] % k == prefix[i] % k→ sum(i+1..j) is divisible by kcount[0] = 1 for the empty prefix
Two prefix sums with the same remainder bound a block whose sum is a multiple of k.
ComplexityTime O(n)Space O(k)We scan the array once and keep a table of size k for the prefix remainders seen so far.

What Trips People Up in Real Interviews

1

Forgetting to normalize negative remainders in C++/Java. -2 % 5 and 3 % 5 must land in the same bucket.

2

Missing the count[0] = 1 seed.

3

Adding count[r] after incrementing it, which counts each prefix as pairing with itself.

4

Using a hash map when an array of size k suffices — not wrong, just slower.

Solution Code

O(n) time
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 res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.