Count Divisible Subarrays — Problem Statement & Solution Guide
Problem Description
Given an array of integers arr and an integer k, count the number of contiguous subarrays where the sum of elements is divisible by k. The subarray can be empty and the sum of an empty subarray is considered as 0, which is divisible by any number.
Examples
Input
[0, 5, 10, 15, 20]
Output
9
Explanation: Step-by-step: 1. Calculate prefix sum: [0, 5, 10, 15, 20]. 2. For each prefix sum, calculate the remainder when divided by 5. 3. Count the number of unique remainders, which represents the number of subarrays divisible by 5.
Input
[-2, -3, 1]
Output
7
Explanation: Step-by-step: 1. Calculate prefix sum: [-2, -1, 0, 1]. 2. For each prefix sum, calculate the remainder when divided by 1. 3. Count the number of unique remainders, which represents the number of subarrays divisible by 1.
Constraints
- 1 <= n <= 3 * 10^4
- 2 <= k <= 10^4
- -10^4 <= arr[i] <= 10^4
Optimal Approach & Strategy
Calculate running sum. Get remainder (sum % k). Handle negative remainders. Use HashMap to store counts of each remainder seen so far. If we see a remainder again, add its previous count to total. Time O(N), Space O(K).
Brute Force Approach
Check all subarrays. Time O(N^2).
Verified Code Solutions
function countDivisibleSubarrays(arr, k) { let count = 0; let prefixSum = 0; let remainderMap = new Map(); remainderMap.set(0, 1); for (let i = 0; i < arr.length; i++) { prefixSum += arr[i]; let remainder = (prefixSum % k + k) % k; if (remainderMap.has(remainder)) { count += remainderMap.get(remainder); } remainderMap.set(remainder, remainderMap.get(remainder) + 1 || 1); } return count; }public int countDivisibleSubarrays(int[] arr, int k) {
int[] prefixSum = new int[arr.length + 1];
prefixSum[0] = 0;
for (int i = 0; i < arr.length; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
Map<Integer, Integer> remainderCount = new HashMap<>();
for (int i = 0; i < prefixSum.length; i++) {
int remainder = prefixSum[i] % k;
remainderCount.put(remainder, remainderCount.getOrDefault(remainder, 0) + 1);
}
return remainderCount.values().stream().mapToInt(Integer::intValue).sum();
}def count_divisible_subarrays(arr, k):
prefix_sum = [0]
for num in arr:
prefix_sum.append(prefix_sum[-1] + num)
remainder_count = {}
for i in range(len(prefix_sum)):
remainder = prefix_sum[i] % k
if remainder in remainder_count:
remainder_count[remainder] += 1
else:
remainder_count[remainder] = 1
return sum(remainder_count.values())function countDivisibleSubarrays(arr, k) { let count = 0; let prefixSum = 0; let remainderMap = new Map(); remainderMap.set(0, 1); for (let i = 0; i < arr.length; i++) { prefixSum += arr[i]; let remainder = (prefixSum % k + k) % k; if (remainderMap.has(remainder)) { count += remainderMap.get(remainder); } remainderMap.set(remainder, remainderMap.get(remainder) + 1 || 1); } return count; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.