Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Subarray Sums Divisible by K

Try it yourself
MediumProblemExternal link

Description

You get an integer array nums and an integer k.

Return the number of non-empty contiguous subarrays whose sum is divisible by k. A sum of 0 counts: 0 is a multiple of every k.

Examples

Example 1

Input: nums = [4, 5, 0, -2, -3, 1], k = 5

Output: 7

Explanation: The 7 subarrays are [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3] and [-2, -3]: each adds up to 0, 5 or 10.

Example 2

Input: nums = [5], k = 9

Output: 0

Explanation: The only subarray, [5], adds up to 5, which isn't a multiple of 9.

Example 3

Input: nums = [-1, 2, 9], k = 2

Output: 2

Explanation: [2] adds up to 2 and [-1, 2, 9] to 10, both even. The running totals -1 and 1 differ by 2, so they must count as the same remainder.

Constraints

  • 1 ≤ nums.length ≤ 3 · 10^4
  • -10^4 ≤ nums[i] ≤ 10^4
  • 2 ≤ k ≤ 10^4

Editorial

Brute Force

Intuition

Check every subarray: for each start, extend it one value at a time, keep a running sum, and count the sums that are multiples of k.

Step-by-Step Explanation

For nums = [4, 5, 0, -2, -3, 1] and k = 5, here is the walk from start 1:

  1. nums[1..1] adds up to 5, a multiple of 5.
  2. nums[1..2] adds up to 5, a multiple of 5.
  3. nums[1..3] adds up to 3, not a multiple of 5.
  4. nums[1..4] adds up to 0, a multiple of 5.
  5. nums[1..5] adds up to 1, not a multiple of 5.
  6. Start 1 gives 3 subarrays. Every other start repeats the walk, which is what makes this O(n²).

Extend One Start — The shaded cells are the subarray being tested; green marks a sum that is a multiple of k.

Algorithm

  1. For each start s, set a running sum to 0.
  2. For each end e from s: add nums[e]; if the sum is a multiple of k, count it.
  3. Return the count.

Code

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size(), count = 0;
        for (int s = 0; s < n; s++) {
            int total = 0;
            for (int e = s; e < n; e++) {       // every subarray that starts at s
                total += nums[e];
                if (total % k == 0) count++;    // 0 checks fine even when total is negative
            }
        }
        return count;
    }
};

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        n, count = len(nums), 0
        for s in range(n):
            total = 0
            for e in range(s, n):               # every subarray that starts at s
                total += nums[e]
                if total % k == 0:
                    count += 1
        return count

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length, count = 0;
        for (int s = 0; s < n; s++) {
            int total = 0;
            for (int e = s; e < n; e++) {       // every subarray that starts at s
                total += nums[e];
                if (total % k == 0) count++;    // 0 checks fine even when total is negative
            }
        }
        return count;
    }
}

var subarraysDivByK = function(nums, k) {
    const n = nums.length;
    let count = 0;
    for (let s = 0; s < n; s++) {
        let total = 0;
        for (let e = s; e < n; e++) {           // every subarray that starts at s
            total += nums[e];
            if (total % k === 0) count++;       // 0 checks fine even when total is negative
        }
    }
    return count;
};

Complexity Analysis

Time Complexity: O(n²)

There are n(n + 1)/2 subarrays.

Space Complexity: O(1)

Why This Approach Is Not Efficient

3 · 10^4 values have about 4.5 · 10^8 subarrays (over the time limit in Python and javascript).

Every subarray sum is the difference of two running totals. A difference is a multiple of k exactly when the two totals leave the same remainder mod k. So instead of trying pairs, count how many earlier totals share each remainder.

Optimal Approach - Counting Remainders

Intuition

Walk once, keeping the running total's remainder mod k. A subarray ending here is divisible by k for every earlier running total with the same remainder, so add how many there were, then count this one. Start the counts with remainder 0 once, for the total before any value, so subarrays that start at index 0 are found too.

Remainders run from 0 to k − 1, so an array of k counts does the job of a hash map. One catch: in C++, Java and JavaScript, % of a negative number is negative (−1 % 5 is −1, where Python gives 4). Shift it with ((r % k) + k) % k so that equal remainders really are equal.

Step-by-Step Explanation

For nums = [4, 5, 0, -2, -3, 1] and k = 5:

  1. The map counts how many running totals had each remainder mod 5. It starts with remainder 0 once, for the total 0 before any value.
  2. Add 4, and the total is 4, remainder 4. Remainder 4 is new, so nothing ends here.
  3. Add 5, and the total is 9, remainder 4. Remainder 4 came up once before, so 1 more subarray ends here and the count is 1.
  4. Add 0, and the total is 9, remainder 4. Remainder 4 came up twice before, so 2 more subarrays end here and the count is 3.
  5. Add −2, and the total is 7, remainder 2. Remainder 2 is new, so nothing ends here.
  6. Add −3, and the total is 4, remainder 4. Remainder 4 came up 3 times before, so 3 more subarrays end here and the count is 6.
  7. Add 1, and the total is 5, remainder 0. Remainder 0 came up once before, so 1 more subarray ends here and the count is 7.
  8. The answer is 7, from a single pass with one lookup and one count per value.

Count Earlier Totals with the Same Remainder — Top: nums and the running total's remainder after each value. Bottom: how many running totals had each remainder so far.

Algorithm

  1. seen = k counts, all 0, then seen[0] = 1; r = 0, count = 0.
  2. For each value x: r = (r + x) mod k, shifted into 0..k − 1; add seen[r] to count; then add 1 to seen[r].
  3. Return count.

Code

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        vector<int> seen(k, 0);                 // remainder -> how many running totals had it
        seen[0] = 1;                            // the total before any value: 0
        int r = 0, count = 0;
        for (int x : nums) {
            r = ((r + x) % k + k) % k;          // % can be negative in C++: shift it into 0..k-1
            count += seen[r];                   // same remainder: the difference is a multiple of k
            seen[r]++;
        }
        return count;
    }
};

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        seen = [0] * k                          # remainder -> how many running totals had it
        seen[0] = 1                             # the total before any value: 0
        r = count = 0
        for x in nums:
            r = (r + x) % k                     # Python's % is already in 0..k-1
            count += seen[r]                    # same remainder: the difference is a multiple of k
            seen[r] += 1
        return count

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] seen = new int[k];                // remainder -> how many running totals had it
        seen[0] = 1;                            // the total before any value: 0
        int r = 0, count = 0;
        for (int x : nums) {
            r = ((r + x) % k + k) % k;          // % can be negative in Java: shift it into 0..k-1
            count += seen[r];                   // same remainder: the difference is a multiple of k
            seen[r]++;
        }
        return count;
    }
}

var subarraysDivByK = function(nums, k) {
    const seen = new Array(k).fill(0);          // remainder -> how many running totals had it
    seen[0] = 1;                                // the total before any value: 0
    let r = 0, count = 0;
    for (const x of nums) {
        r = ((r + x) % k + k) % k;              // % can be negative in JavaScript: shift it into 0..k-1
        count += seen[r];                       // same remainder: the difference is a multiple of k
        seen[r]++;
    }
    return count;
};

Complexity Analysis

Time Complexity: O(n + k)

One pass over nums, and the k counts to set up.

Space Complexity: O(k)

Keeping the remainder instead of the total also keeps every number small, so nothing can overflow.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Using % as it is in Java, C++ or JavaScript. int r = total % k;

On nums = [-1, 2, 9], k = 2 in Java, it returns 1; the answer is 2. In Java (and C++ and JavaScript) % keeps the sign of the left side: -1 % 2 is -1, while 1 % 2 is 1. The running totals -1 and 1 differ by 2, so they should share a remainder, but they get two different keys and never meet. Shift the remainder into 0..k-1 with ((total % k) + k) % k.

Starting with an empty count. seen = [0] * k

On nums = [5, 5], k = 5, it returns 1; the answer is 3. A subarray that starts at index 0 pairs with the total before any value, which is 0. Without seen[0] = 1 at the start, those subarrays are never counted: on [5, 5] with k = 5 it finds 1 of the 3.

Recording before counting. seen[r] += 1 # then count += seen[r]

On nums = [5], k = 9, it returns 1; the answer is 0. Counting after recording lets each running total pair with itself, an empty subarray: every value adds one too many. Look up first, then record.

Testing only the running totals. if total % k == 0: count += 1

On nums = [4, 5, 0, -2, -3, 1], k = 5, it returns 1; the answer is 7. Checking whether each running total is a multiple of k only tests the subarrays that start at index 0. Two totals with the same remainder also make a subarray divisible by k, wherever it starts.

Where This Pattern Is Taught

This problem practises counting subarrays with running totals and a hash map, using remainders. It's taught in Prefix Sums with a Hash Map.