Subarray Sums Divisible by K
Problem 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.
Examples:
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]
Input: nums = [5], k = 9
Output: 0
Explanation: The only subarray of nums = [5] is the array itself: [5], which is not divisible by 9 (5 % 9 ≠ 0).
Constraints:
1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴
Brute Force Approach
When we read the problem statement, the first idea that comes to mind is simple:
We need to check all possible subarrays of the given array, calculate their sums, and check if the sum is divisible by k. If it is, we increase the count. At the end, we just return the total count of such subarrays.
How can we do it?
We can use a brute-force solution by traversing through the array.
For each element, we'll calculate the sum of all subarrays starting from that element by adding the subsequent elements one by one.
As we calculate the sum for each subarray, we check if it's divisible by k. We repeat this process for every element in the array and keep a count of how many subarrays have a sum divisible by k.
Let's understand with an example:
Let nums = [4, 5, 0, -2, -3, 1] and k = 5:
- Start from the first element (index 0: 4):
- Subarray: [4], Sum = 4 (Not divisible by 5)
- Subarray: [4, 5], Sum = 9 (Not divisible by 5)
- Subarray: [4, 5, 0], Sum = 9 (Not divisible by 5)
- Subarray: [4, 5, 0, -2], Sum = 7 (Not divisible by 5)
- Subarray: [4, 5, 0, -2, -3], Sum = 4 (Not divisible by 5)
- Subarray: [4, 5, 0, -2, -3, 1], Sum = 5 (Divisible by 5) → Count = 1
- Move to the second element (index 1: 5):
- Subarray: [5], Sum = 5 (Divisible by 5) → Count = 2
- Subarray: [5, 0], Sum = 5 (Divisible by 5) → Count = 3
- Subarray: [5, 0, -2], Sum = 3 (Not divisible by 5)
- Subarray: [5, 0, -2, -3], Sum = 0 (Divisible by 5) → Count = 4
- Subarray: [5, 0, -2, -3, 1], Sum = 1 (Not divisible by 5)
- Move to the third element (index 2: 0):
- Subarray: [0], Sum = 0 (Divisible by 5) → Count = 5
- Subarray: [0, -2], Sum = -2 (Not divisible by 5)
- Subarray: [0, -2, -3], Sum = -5 (Divisible by 5) → Count = 6
- Subarray: [0, -2, -3, 1], Sum = -4 (Not divisible by 5)
- Move to the fourth element (index 3: -2):
- Subarray: [-2], Sum = -2 (Not divisible by 5)
- Subarray: [-2, -3], Sum = -5 (Divisible by 5) → Count = 7
- Subarray: [-2, -3, 1], Sum = -4 (Not divisible by 5)
- Move to the fifth element (index 4: -3):
- Subarray: [-3], Sum = -3 (Not divisible by 5)
- Subarray: [-3, 1], Sum = -2 (Not divisible by 5)
- Move to the sixth element (index 5: 1):
- Subarray: [1], Sum = 1 (Not divisible by 5)
Final Count: 7
Thus, the number of subarrays with a sum divisible by 5 is 7.
How to implement it in code:
- Create a variable count and set it to 0 (to keep track of subarrays whose sum is divisible by k).
- Get the size of the array nums.
- Iterate through the array with an index i (starting point of the subarray).
- For each starting point i, initialize current_sum to 0.
- Iterate through the array from index i to the end (extend the subarray).
- Add the current element to current_sum.
- For each current_sum, check if it is divisible by k.
- If true, increment the count.
- After both loops, return count.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
// Initialize count of subarrays
int count = 0;
// Size of the array
int n = nums.size();
// Outer loop: starting point of subarray
for (int i = 0; i < n; i++) {
// Initialize sum for subarrays starting at i
int current_sum = 0;
// Inner loop: calculate sum of subarrays starting at i
for (int j = i; j < n; j++) {
// Add current element to sum
current_sum += nums[j];
// Check if the current sum is divisible by k
if (current_sum % k == 0) {
// Increment count if divisible
count++;
}
}
}
// Return total count of subarrays
return count;
}
};2. Java Try on Compiler
class Solution {
public int subarraysDivByK(int[] nums, int k) {
// Initialize count of subarrays
int count = 0;
// Size of the array
int n = nums.length;
// Outer loop: starting point of subarray
for (int i = 0; i < n; i++) {
// Initialize sum for subarrays starting at i
int current_sum = 0;
// Inner loop: calculate sum of subarrays starting at i
for (int j = i; j < n; j++) {
// Add current element to sum
current_sum += nums[j];
// Check if the current sum is divisible by k
if (current_sum % k == 0) {
// Increment count if divisible
count++;
}
}
}
// Return total count of subarrays
return count;
}
}
3. Python Try on Compiler
class Solution:
def subarraysDivByK(self, nums, k):
# Initialize count of subarrays
count = 0
# Size of the array
n = len(nums)
# Outer loop: starting point of subarray
for i in range(n):
# Initialize sum for subarrays starting at i
current_sum = 0
# Inner loop: calculate sum of subarrays starting at i
for j in range(i, n):
# Add current element to sum
current_sum += nums[j]
# Check if the current sum is divisible by k
if current_sum % k == 0:
# Increment count if divisible
count += 1
# Return total count of subarrays
return count
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraysDivByK = function(nums, k) {
// Initialize count of subarrays
let count = 0;
// Size of the array
let n = nums.length;
// Outer loop: starting point of subarray
for (let i = 0; i < n; i++) {
// Initialize sum for subarrays starting at i
let current_sum = 0;
// Inner loop: calculate sum of subarrays starting at i
for (let j = i; j < n; j++) {
// Add current element to sum
current_sum += nums[j];
// Check if the current sum is divisible by k
if (current_sum % k === 0) {
// Increment count if divisible
count++;
}
}
}
// Return total count of subarrays
return count;
};Time Complexity: O(n²)
The outer loop iterates from i = 0 to n - 1. This means the outer loop executes n times.
For each iteration of the outer loop (with a fixed starting point i), the inner loop iterates from i to n - 1.
The total number of iterations across all outer and inner loops is therefore the sum:
n + (n - 1) + (n - 2) + ... + 1.
The above sum can be computed using the formula for the sum of the first n natural numbers:
S = (n * (n + 1)) / 2.
Substituting into the formula, the total number of iterations is proportional to n², which dominates the time complexity.
Hence, the time complexity of the brute force solution is O(n²).
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
The solution uses only a few variables (count, current_sum, loop indices) are used, which require O(1) space.
Total Space Complexity: O(n)
The input array nums is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁴. This means that for each test case, where the size of the array is at most 10⁴, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10⁸ operations (for n = 10⁴), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁴, the solution with 10⁸ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10⁸ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes, of course!
We can definitely optimize it—let's do it!
In the previous approach, we checked all possible subarrays, calculated their sums, and then checked if they were divisible by k. While it worked, it wasn't feasible because it gave us an O(n²) solution.
But don't worry—here’s how we can make it efficient!
Now, let’s analyze the drawback in our previous approach.
The issue was that we calculated the sum of every possible subarray. That’s where we lost efficiency—doing redundant work over and over.
Let’s fix this by eliminating the need to recompute sums repeatedly.
Yes, exactly! Let’s break it down step by step.
What do we do to get the sum of a subarray from index 0 to i?
We just calculate the sum of all elements from the start to index i, right?
But what if there’s an index j somewhere between 0 and i, and now you need the sum of the subarray from j to i?
Simple! You calculate the sum from 0 to i and subtract the sum from 0 to j-1. Easy, right?
Now, to make it efficient, we can precompute and store the sum up to each index in an array. This allows us to quickly get the sum of any subarray by subtracting one precomputed value from another.
Got it? Great! But wait... how does this help us determine how many subarray sums are divisible by k?
Let’s think about it with an example.
Suppose we have a sequence :
5, 10, 15, 20..., and let’s say k = 5.
What’s common here?
If we take these elements modulo k, they all become 0:
5 % 5 = 0, 10 % 5 = 0, 15 % 5 = 0...
So, whenever we add k (or a multiple of k) to an element that’s already divisible by k, the new element will also be divisible by k.
For example:
- Starting with 5, we add 5 (k) to get 10, which is also divisible by k.
- Adding 10 (2*k) gives 15, which is still divisible.
Now observe the pattern:
If you previously encountered a 0 in element % k and encounter it again later, there’s a subarray between these two occurrences whose sum is a multiple of k!
In general, if you add any multiple of k to a number divisible by k, it will also be divisible by k.
Let’s take another example:
Sequence: 8, 13, 18..., and k = 5.
- 13 - 8 = 5, divisible by 5.
- 18 - 13 = 5, divisible by 5.
- 18 - 8 = 10, divisible by 5.
Now, if we take the modulo k of each sum:
8 % 5 = 3, 13 % 5 = 3, 18 % 5 = 3.
Notice something?
Here, too, if you encounter the same remainder (like 3) more than once, it means there’s a subarray between these occurrences whose sum is divisible by k.
In general, if you encounter the same remainder more than once, it means there is a subarray whose sum is a multiple of kkk between the two occurrences of that remainder.
So, the observation is clear:
- Instead of storing the entire sum, store the modulo k of each sum.
- If the same remainder is encountered again, there’s a subarray in between whose sum is a multiple of k.
But wait! What if the prefix sum modulo k is negative?
Since the numbers in the array can range from [−10⁴,10⁴], getting a negative sum is quite possible.
In such cases, the sum modulo k will be at most −(k−1). However, storing a negative modulo value won’t give the desired result.
For example, if the sum is −2 and k=5,
When we calculate −2%5 ,we get: −2%5=−2
This gives a negative value. However, if we try to compare this negative remainder to other positive remainders, such as for 3 and 8, we would encounter issues.
Let’s now take some numbers and apply the modulo operation with k=5:
- 3%5=3
- 8%5=3
We see that both 3 and 8 give a remainder of 3 when divided by 5. Now, let's subtract the remainder −2 from 3 and 8:
- 3−(−2)=5
- 8−(−2)=10
Both of these values are divisible by 5, meaning they are multiples of k. However, if we check the hash values for −2 and 3 or 8, they would be treated as different entries in a hash map.
This is where adding k to negative remainders becomes essential. Without adding k, the modulo values are inconsistent (i.e., negative remainders would differ from positive ones), which can cause issues when trying to store and compare values in a hash map.
To make the map consistent, we add k to any negative remainder:
- −2+5=3
Now, the remainder for −2 becomes 3, the same as the remainders for 3 and 8. This ensures that all the values map to the same key, and the subarray sum logic remains correct.
By adding k to negative remainders, we make sure that the modulo operation produces consistent, positive results. This avoids issues where negative remainders would cause incorrect mappings in hash maps or sets. It ensures that values like −2 and positive values like 3 or 8, which are equivalent modulo k, are treated the same in our algorithm.
Therefore, we can see that adding a multiple of k to a negative sum does not yield the same remainder. Hence, storing a negative sum is not beneficial for our calculations.
To overcome this problem we can add k to a negative modulo value ensures that all remainders fall within the positive range [0, k−1], making them consistent and easier to work with.
Therefore, to handle negative modulo values effectively, we always add k to the negative result of sum%k. This ensures all modulo values are positive and consistent for further processing.
This insight helps us optimize the problem significantly! Let’s build on this idea to create an efficient solution.
Steps to do it:
- Calculate the prefix sum incrementally as you iterate through the array.
- Track the count of subarrays whose sums are divisible by k.
- Mod all prefix sums by k to reduce the sums into manageable ranges (0 to k-1).
- If the prefix sum modulo k is negative, add k to it to handle cases with negative values.
(This ensures that the remainder stays in the range [0, k-1]). - Use a hashmap (or dictionary) to store the frequency of each remainder (modulo k).
- For every prefix sum's remainder:If the remainder has been seen before, it means subarrays exist between the previous occurrence and the current index whose sum is divisible by k.Add the frequency of this remainder in the hashmap to the total count.
- Update the hashmap by incrementing the frequency of the current remainder.
- Return the total count at the end.
Let's understand with an example:
Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Initialization: prefix_sum = 0, count = 0, remainder_map = {0: 1}
- Add 4 → prefix_sum = 4
remainder = 4 (4%5).
Add to map → {0: 1, 4: 1}
count = 0. - Add 5 → prefix_sum = 9
remainder = 4(9%5).
Found in map (1 occurrence) → count = 1
update map → {0: 1, 4: 2}. - Add 0 → prefix_sum = 9
remainder = 4(9%5).
Found in map (2 occurrences) → count = 3
update map → {0: 1, 4: 3}. - Add -2 → prefix_sum = 7
remainder = 2(7%5).
Add to map → {0: 1, 4: 3, 2: 1}
count = 3. - Add -3 → prefix_sum = 4 (7-3 = 4)
remainder = 4(4%5).
Found in map (3 occurrences) → count = 6
update map → {0: 1, 4: 4, 2: 1}. - Add 1 → prefix_sum = 5
remainder = 0 (5%5 = 0).
Found in map (1 occurrence) → count = 7
update map → {0: 2, 4: 4, 2: 1}.
Result: count = 7.
How to code it up:
- A variable prefix_sum to calculate the running cumulative sum.
- A hashmap (unordered_map) to store the frequency of remainders (mod k).
- A variable count to store the total number of subarrays divisible by k.
- Add the current element to prefix_sum.
- Compute remainder = prefix_sum % k.
- If remainder is negative, add k to normalize it into the range [0, k-1].
- If the remainder exists in the hashmap, it means there are subarrays whose sum is divisible by k. Add the frequency of the remainder to count.
- Increment the frequency of the current remainder in the hashmap.
- After iterating through the array, return count.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
int prefix_sum = 0, count = 0;
unordered_map<int, int> remainder_map;
// To handle subarrays starting from index 0
remainder_map[0] = 1;
for (int num : nums) {
prefix_sum += num;
// Compute remainder and normalize it
int remainder = prefix_sum % k;
if (remainder < 0) {
remainder += k;
}
// Add to count if remainder already exists
if (remainder_map.find(remainder) != remainder_map.end()) {
count += remainder_map[remainder];
}
// Update the frequency of the current remainder
remainder_map[remainder]++;
}
return count;
}
};2. Java Try on Compiler
import java.util.HashMap;
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int prefix_sum = 0, count = 0;
HashMap<Integer, Integer> remainder_map = new HashMap<>();
// To handle subarrays starting from index 0
remainder_map.put(0, 1);
for (int num : nums) {
prefix_sum += num;
// Compute remainder and normalize it
int remainder = prefix_sum % k;
if (remainder < 0) {
remainder += k;
}
// Add to count if remainder already exists
if (remainder_map.containsKey(remainder)) {
count += remainder_map.get(remainder);
}
// Update the frequency of the current remainder
remainder_map.put(remainder, remainder_map.getOrDefault(remainder, 0) + 1);
}
return count;
}
}
3. Python Try on Compiler
class Solution:
def subarraysDivByK(self, nums, k):
prefix_sum = 0
count = 0
remainder_map = {0: 1} # To handle subarrays starting from index 0
for num in nums:
prefix_sum += num
# Compute remainder and normalize it
remainder = prefix_sum % k
if remainder < 0:
remainder += k
# Add to count if remainder already exists
count += remainder_map.get(remainder, 0)
# Update the frequency of the current remainder
remainder_map[remainder] = remainder_map.get(remainder, 0) + 1
return count
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraysDivByK = function(nums, k) {
let prefix_sum = 0, count = 0;
let remainder_map = { 0: 1 }; // To handle subarrays starting from index 0
for (let num of nums) {
prefix_sum += num;
// Compute remainder and normalize it
let remainder = prefix_sum % k;
if (remainder < 0) {
remainder += k;
}
// Add to count if remainder already exists
if (remainder in remainder_map) {
count += remainder_map[remainder];
}
// Update the frequency of the current remainder
remainder_map[remainder] = (remainder_map[remainder] || 0) + 1;
}
return count;
};
Time Complexity: O(n)
The loop runs once for each element in the array (nums), so the time complexity for this part is O(n).
Calculating the prefix sum and the remainder is done in constant time, i.e., O(1).
The remainder_map operations (checking if a remainder exists and updating it) are O(1) on average, since unordered_map (C++), HashMap (Java), and objects/dictionaries (Python, JavaScript) provide constant-time lookups and insertions on average.
Therefore, the overall time complexity is O(n).
Space Complexity: O(n+k)
- Auxiliary Space Complexity: O(k)
The main auxiliary space comes from the remainder_map, which stores the frequency of each remainder encountered during the iteration.
In the worst case, there could be k different remainders (ranging from 0 to k-1), so the space used by remainder_map is O(k). - Total Space Complexity: O(n)
The input array nums is of size n, which requires O(n) space.
Thus, the total space complexity is O(n) for the input array plus O(k) for the remainder map, Therefore, the total space complexity is O(n+k).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.