LeetCode 0974. Subarray Sums Divisible by K Solution in Java, C++, Python & More | Explanation + Code

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 ≤ j such that the sum of nums[i,..j] is divisible by k. If we let s_i represent the sum of nums[0,..i] and s_j represent the sum of 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 cnt to count the number of prefix sums modulo k, where cnt[i] represents the number of prefix sums with a modulo k value of i. Initially, cnt[0] = 1. We use a variable s to represent the prefix sum, initially s = 0.

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

In the end, we return the answer 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 nums.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)