Skip to content

974. Subarray Sums Divisible by K

Description

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 <= 3 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

Solutions

Solution 1: Hash Table + Prefix Sum

Suppose there exists \(i \leq j\) such that the sum of \(\textit{nums}[i,..j]\) is divisible by \(k\). If we let \(s_i\) represent the sum of \(\textit{nums}[0,..i]\) and \(s_j\) represent the sum of \(\textit{nums}[0,..j]\), then \(s_j - s_i\) is divisible by \(k\), i.e., \((s_j - s_i) \bmod k = 0\), which means \(s_j \bmod k = s_i \bmod k\). Therefore, we can use a hash table to count the number of prefix sums modulo \(k\), allowing us to quickly determine if there exists a subarray that meets the condition.

We use a hash table \(\textit{cnt}\) to count the number of prefix sums modulo \(k\), where \(\textit{cnt}[i]\) represents the number of prefix sums with a modulo \(k\) value of \(i\). Initially, \(\textit{cnt}[0] = 1\). We use a variable \(s\) to represent the prefix sum, initially \(s = 0\).

Next, we traverse the array \(\textit{nums}\) from left to right. For each element \(x\), we calculate \(s = (s + x) \bmod k\), then update the answer \(\textit{ans} = \textit{ans} + \textit{cnt}[s]\), where \(\textit{cnt}[s]\) represents the number of prefix sums with a modulo \(k\) value of \(s\). Finally, we increment the value of \(\textit{cnt}[s]\) by \(1\) and continue to the next element.

In the end, we return the answer \(\textit{ans}\).

Note: Since the value of \(s\) can be negative, we can add \(k\) to the result of \(s \bmod k\) and then take modulo \(k\) again to ensure that the value of \(s\) is non-negative.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
8
9
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = s = 0
        for x in nums:
            s = (s + x) % k
            ans += cnt[s]
            cnt[s] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1);
        int ans = 0, s = 0;
        for (int x : nums) {
            s = ((s + x) % k + k) % k;
            ans += cnt.getOrDefault(s, 0);
            cnt.merge(s, 1, Integer::sum);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> cnt{{0, 1}};
        int ans = 0, s = 0;
        for (int& x : nums) {
            s = ((s + x) % k + k) % k;
            ans += cnt[s]++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func subarraysDivByK(nums []int, k int) (ans int) {
    cnt := map[int]int{0: 1}
    s := 0
    for _, x := range nums {
        s = ((s+x)%k + k) % k
        ans += cnt[s]
        cnt[s]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function subarraysDivByK(nums: number[], k: number): number {
    const cnt: { [key: number]: number } = { 0: 1 };
    let s = 0;
    let ans = 0;
    for (const x of nums) {
        s = (((s + x) % k) + k) % k;
        ans += cnt[s] || 0;
        cnt[s] = (cnt[s] || 0) + 1;
    }
    return ans;
}

Comments