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 <= 104To solve #974 Subarray Sums Divisible by K, the key idea is to use prefix sums combined with a hash table. Instead of checking every possible subarray (which would be inefficient), we track the cumulative sum while iterating through the array.
For each index, compute the running sum and store the remainder when dividing by k. If two prefix sums have the same remainder when taken modulo k, the subarray between them has a sum divisible by k. A hash map can store the frequency of each remainder encountered so far, allowing us to quickly count how many valid subarrays end at the current index.
This approach efficiently transforms the problem into counting matching remainders while scanning the array once. Compared to brute-force methods that check every subarray, the prefix sum + hash map technique significantly reduces the time complexity while using additional space to track remainder frequencies.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum with Hash Map | O(n) | O(k) |
take U forward
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int subarraysDivByK(int* nums, int numsSize, int k) {
5
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Using modulo k helps identify when two prefix sums differ by a multiple of k. If two cumulative sums produce the same remainder, their difference is divisible by k, which means the subarray between them satisfies the condition.
Yes, variations of this problem are commonly asked in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of prefix sums, modular arithmetic, and hash map optimization techniques.
A hash map (or frequency array) is the most useful data structure for this problem. It stores how many times each remainder of prefix sum modulo k has appeared, enabling quick counting of valid subarrays.
The optimal approach uses prefix sums along with a hash map to track remainders of cumulative sums modulo k. If the same remainder appears multiple times, the subarray between those indices has a sum divisible by k. This allows the problem to be solved in linear time.
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.