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] <= 1042 <= k <= 104Problem Overview: Given an integer array nums and an integer k, count the number of contiguous subarrays whose sum is divisible by k. The key observation: if two prefix sums leave the same remainder when divided by k, the subarray between them has a sum divisible by k.
Approach 1: Brute Force Subarray Sum (O(n²) time, O(1) space)
Check every possible subarray. Start an index i, then extend the subarray to every j ≥ i while maintaining the running sum. Each time the sum modulo k equals zero, increment the count. This method directly simulates the definition of the problem and helps build intuition about how subarray sums behave. However, the nested iteration over all start and end indices leads to O(n²) time complexity, which becomes slow for large inputs.
Approach 2: Prefix Sums with HashMap (O(n) time, O(k) space)
Use a running prefix sum and track the frequency of remainders prefixSum % k in a hash map. When the same remainder appears again, the subarray between the two indices has a sum divisible by k. For each element, compute the new prefix sum, normalize the remainder using (sum % k + k) % k to handle negative numbers, and check how many times this remainder has appeared before. Add that frequency to the result, then update the map. This transforms the problem into counting matching remainder pairs using a constant‑time hash lookup.
The insight is rooted in prefix sum arithmetic: if prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, meaning the subarray i+1..j is divisible by k. The hash map stores counts of each remainder so you can accumulate valid subarrays in a single pass.
This solution combines ideas from Prefix Sum, Hash Table, and Array problems. The single linear traversal and constant-time hash operations make it the optimal strategy for large arrays.
Recommended for interviews: Interviewers expect the prefix sum + hash map approach. Brute force demonstrates that you understand subarrays and modular checks, but the O(n) prefix remainder counting technique shows deeper algorithmic thinking and familiarity with common prefix-sum patterns.
This approach leverages prefix sums and the properties of modular arithmetic to efficiently count subarrays whose sums are divisible by k. By maintaining a hashmap (or dictionary) that keeps track of the frequency of each remainder observed when computing prefix sums modulo k, we can determine how many valid subarrays end at each position in the array.
For any position in the array, if we have the same remainder as a previously computed prefix sum, it indicates that the subarray between the two indices is divisible by k.
In this C implementation, an array is used to store the frequency of each remainder when the cumulative sum is divided by k. We initialize the first element to 1 as a subarray with sum 0 (no elements) is considered valid when dividing by k. We then iterate over the input array, updating the cumulative sum and calculating the current remainder. Each time we find a previously seen remainder in our modCount array, it indicates subarrays ending at the current position are divisible by k.
Time Complexity: O(n), where n is the number of elements in the array, as we iterate over the array once.
Space Complexity: O(k), where k is the number of different remainders we track in our modCount array.
The brute force approach involves checking all possible subarrays to find those whose sum is divisible by k. This method is less efficient and should be used primarily for small inputs due to its higher time complexity. We iterate over all subarray starting points and compute the sum for all possible ending positions, counting subarrays that meet the criteria.
This C implementation follows a nested loop technique. The first loop sets potential starting points for subarrays, and the inner loop accumulates sums for subarrays ending at each subsequent index. Each valid subarray whose sum is zero modulo k is counted. This approach is simple but becomes inefficient as input sizes grow.
Time Complexity: O(n^2), where n is the number of elements in the array (due to double loop).
Space Complexity: O(1), as only integer counters and accumulators are used.
Suppose there exists i leq 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
scan be negative, we can addkto the result ofs bmod kand then take modulokagain to ensure that the value ofsis non-negative.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sums with HashMap | Time Complexity: O(n), where n is the number of elements in the array, as we iterate over the array once. |
| Brute Force Subarray Sum | Time Complexity: O(n^2), where n is the number of elements in the array (due to double loop). |
| Hash Table + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Sum | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum + HashMap | O(n) | O(k) | General case and expected interview solution for large arrays |
Subarrays Sums Divisible by K (Leetcode 974) Algorithm Explained • Pepcoding • 72,963 views views
Watch 9 more video solutions →Practice Subarray Sums Divisible by K with our built-in code editor and test cases.
Practice on FleetCode