974. Subarray Sums Divisible by K - Explanation

Description

You are given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

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

Output: 7

Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9

Output: 0

Constraints:

1 <= nums.length <= 30,000
-10,000 <= nums[i] <= 10,000
2 <= k <= 10,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Prefix Sums - The solution uses prefix sums to efficiently compute subarray sums
Modular Arithmetic - Understanding how remainders work, especially that two numbers with the same remainder mod k have a difference divisible by k
Hash Maps - Used to count occurrences of each remainder for efficient lookup

1. Brute Force

Intuition

The simplest approach checks every possible subarray. For each starting index, we extend the subarray one element at a time, keeping a running sum. If the sum is divisible by k (i.e., sum % k == 0), we count it.

Algorithm

Initialize res = 0.
For each starting index i:
- Set curSum = 0.
- For each ending index j from i to n - 1:
  - Add nums[j] to curSum.
  - If curSum % k == 0, increment res.
Return res.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += nums[j]
                if curSum % k == 0:
                    res += 1

        return res

public class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length, res = 0;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += nums[j];
                if (curSum % k == 0) {
                    res++;
                }
            }
        }

        return res;
    }
}

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size(), res = 0;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += nums[j];
                if (curSum % k == 0) {
                    res++;
                }
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    subarraysDivByK(nums, k) {
        const n = nums.length;
        let res = 0;

        for (let i = 0; i < n; i++) {
            let curSum = 0;
            for (let j = i; j < n; j++) {
                curSum += nums[j];
                if (curSum % k === 0) {
                    res++;
                }
            }
        }

        return res;
    }
}

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        int n = nums.Length, res = 0;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += nums[j];
                if (curSum % k == 0) {
                    res++;
                }
            }
        }

        return res;
    }
}

func subarraysDivByK(nums []int, k int) int {
    n, res := len(nums), 0

    for i := 0; i < n; i++ {
        curSum := 0
        for j := i; j < n; j++ {
            curSum += nums[j]
            if curSum%k == 0 {
                res++
            }
        }
    }

    return res
}

class Solution {
    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        val n = nums.size
        var res = 0

        for (i in 0 until n) {
            var curSum = 0
            for (j in i until n) {
                curSum += nums[j]
                if (curSum % k == 0) {
                    res++
                }
            }
        }

        return res
    }
}

class Solution {
    func subarraysDivByK(_ nums: [Int], _ k: Int) -> Int {
        let n = nums.count
        var res = 0

        for i in 0..<n {
            var curSum = 0
            for j in i..<n {
                curSum += nums[j]
                if curSum % k == 0 {
                    res += 1
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut res = 0;

        for i in 0..n {
            let mut cur_sum = 0;
            for j in i..n {
                cur_sum += nums[j];
                if cur_sum % k == 0 {
                    res += 1;
                }
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix Sum + Hash Map

Intuition

If two prefix sums have the same remainder when divided by k, their difference is divisible by k. So the subarray between those two positions has a sum divisible by k. We use a hash map to count how many times each remainder has appeared. For each new prefix sum, we check how many previous prefix sums share the same remainder.

Algorithm

Initialize prefixSum = 0, res = 0, and a hash map prefixCnt with {0: 1}.
For each number in the array:
- Add it to prefixSum.
- Compute remain = prefixSum % k. Handle negative remainders by adding k if needed.
- Add prefixCnt[remain] to res.
- Increment prefixCnt[remain] by 1.
Return res.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix_sum = 0
        res = 0
        prefix_cnt = defaultdict(int)
        prefix_cnt[0] = 1

        for n in nums:
            prefix_sum += n
            remain = prefix_sum % k

            res += prefix_cnt[remain]
            prefix_cnt[remain] += 1

        return res

public class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int prefixSum = 0, res = 0;
        Map<Integer, Integer> prefixCnt = new HashMap<>();
        prefixCnt.put(0, 1);

        for (int n : nums) {
            prefixSum += n;
            int remain = prefixSum % k;
            if (remain < 0) remain += k;

            res += prefixCnt.getOrDefault(remain, 0);
            prefixCnt.put(remain, prefixCnt.getOrDefault(remain, 0) + 1);
        }

        return res;
    }
}

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixSum = 0, res = 0;
        unordered_map<int, int> prefixCnt;
        prefixCnt[0] = 1;

        for (int n : nums) {
            prefixSum += n;
            int remain = prefixSum % k;
            if (remain < 0) remain += k;

            res += prefixCnt[remain];
            prefixCnt[remain]++;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    subarraysDivByK(nums, k) {
        let prefixSum = 0,
            res = 0;
        const prefixCnt = new Map();
        prefixCnt.set(0, 1);

        for (let n of nums) {
            prefixSum += n;
            let remain = prefixSum % k;
            if (remain < 0) remain += k;

            res += prefixCnt.get(remain) || 0;
            prefixCnt.set(remain, (prefixCnt.get(remain) || 0) + 1);
        }

        return res;
    }
}

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        int prefixSum = 0, res = 0;
        Dictionary<int, int> prefixCnt = new Dictionary<int, int>();
        prefixCnt[0] = 1;

        foreach (int n in nums) {
            prefixSum += n;
            int remain = prefixSum % k;
            if (remain < 0) remain += k;

            if (prefixCnt.ContainsKey(remain)) {
                res += prefixCnt[remain];
                prefixCnt[remain]++;
            } else {
                prefixCnt[remain] = 1;
            }
        }

        return res;
    }
}

func subarraysDivByK(nums []int, k int) int {
    prefixSum, res := 0, 0
    prefixCnt := make(map[int]int)
    prefixCnt[0] = 1

    for _, n := range nums {
        prefixSum += n
        remain := prefixSum % k
        if remain < 0 {
            remain += k
        }

        res += prefixCnt[remain]
        prefixCnt[remain]++
    }

    return res
}

class Solution {
    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        var prefixSum = 0
        var res = 0
        val prefixCnt = HashMap<Int, Int>()
        prefixCnt[0] = 1

        for (n in nums) {
            prefixSum += n
            var remain = prefixSum % k
            if (remain < 0) remain += k

            res += prefixCnt.getOrDefault(remain, 0)
            prefixCnt[remain] = prefixCnt.getOrDefault(remain, 0) + 1
        }

        return res
    }
}

class Solution {
    func subarraysDivByK(_ nums: [Int], _ k: Int) -> Int {
        var prefixSum = 0
        var res = 0
        var prefixCnt: [Int: Int] = [0: 1]

        for n in nums {
            prefixSum += n
            var remain = prefixSum % k
            if remain < 0 { remain += k }

            res += prefixCnt[remain, default: 0]
            prefixCnt[remain, default: 0] += 1
        }

        return res
    }
}

impl Solution {
    pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 {
        let mut prefix_sum = 0;
        let mut res = 0;
        let mut prefix_cnt = HashMap::new();
        prefix_cnt.insert(0, 1);

        for &n in &nums {
            prefix_sum += n;
            let mut remain = prefix_sum % k;
            if remain < 0 {
                remain += k;
            }

            res += prefix_cnt.get(&remain).unwrap_or(&0);
            *prefix_cnt.entry(remain).or_insert(0) += 1;
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(k)$

3. Prefix Sum + Array

Intuition

Since remainders when dividing by k are always in the range [0, k-1], we can use a fixed-size array instead of a hash map. This gives slightly better constant factors. We also handle negative numbers by adding k to the modulo result, ensuring all remainders are non-negative.

Algorithm

Create an array count of size k, initialized to zeros, with count[0] = 1.
Initialize prefix = 0 and res = 0.
For each number in the array:
- Update prefix = (prefix + num % k + k) % k to handle negatives.
- Add count[prefix] to res.
- Increment count[prefix].
Return res.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        count = [0] * k
        count[0] = 1
        prefix = res = 0

        for num in nums:
            prefix = (prefix + num + k) % k
            res += count[prefix]
            count[prefix] += 1

        return res

public class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] count = new int[k];
        count[0] = 1;
        int prefix = 0, res = 0;

        for (int num : nums) {
            prefix = (prefix + num % k + k) % k;
            res += count[prefix];
            count[prefix]++;
        }

        return res;
    }
}

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        vector<int> count(k, 0);
        count[0] = 1;
        int prefix = 0, res = 0;

        for (int num : nums) {
            prefix = (prefix + num % k + k) % k;
            res += count[prefix];
            count[prefix]++;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    subarraysDivByK(nums, k) {
        const count = Array(k).fill(0);
        count[0] = 1;
        let prefix = 0,
            res = 0;

        for (let num of nums) {
            prefix = (prefix + (num % k) + k) % k;
            res += count[prefix];
            count[prefix]++;
        }

        return res;
    }
}

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        int[] count = new int[k];
        count[0] = 1;
        int prefix = 0, res = 0;

        foreach (int num in nums) {
            prefix = (prefix + num % k + k) % k;
            res += count[prefix];
            count[prefix]++;
        }

        return res;
    }
}

func subarraysDivByK(nums []int, k int) int {
    count := make([]int, k)
    count[0] = 1
    prefix, res := 0, 0

    for _, num := range nums {
        prefix = (prefix + num%k + k) % k
        res += count[prefix]
        count[prefix]++
    }

    return res
}

class Solution {
    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        val count = IntArray(k)
        count[0] = 1
        var prefix = 0
        var res = 0

        for (num in nums) {
            prefix = (prefix + num % k + k) % k
            res += count[prefix]
            count[prefix]++
        }

        return res
    }
}

class Solution {
    func subarraysDivByK(_ nums: [Int], _ k: Int) -> Int {
        var count = [Int](repeating: 0, count: k)
        count[0] = 1
        var prefix = 0
        var res = 0

        for num in nums {
            prefix = (prefix + num % k + k) % k
            res += count[prefix]
            count[prefix] += 1
        }

        return res
    }
}

impl Solution {
    pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut count = vec![0i32; k];
        count[0] = 1;
        let mut prefix = 0i32;
        let mut res = 0;

        for &num in &nums {
            prefix = ((prefix + num % k as i32) + k as i32) % k as i32;
            res += count[prefix as usize];
            count[prefix as usize] += 1;
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n + k)$
Space complexity: $O(k)$

Common Pitfalls

Mishandling Negative Remainders

In most programming languages, the modulo of a negative number can return a negative result (e.g., -5 % 3 = -2 in Java/C++). You must normalize the remainder to be non-negative by using ((prefixSum % k) + k) % k to ensure correct hash map lookups.

Confusing This Problem with Subarray Sum Equals K

While both problems use prefix sums, the comparison logic differs. Here you need to match remainders, not exact differences. Two prefix sums with the same remainder modulo k indicate a valid subarray, regardless of their absolute values.

Forgetting to Initialize Count for Remainder Zero

The hash map or array must start with count[0] = 1 to account for subarrays starting from index 0 that are directly divisible by k. Missing this initialization causes undercounting.