Count Divisible Subarrays — Problem Statement & Solution Guide
Problem Description
Given an integer array nums and a positive integer k, determine how many contiguous subarrays have a sum that is an exact multiple of k. The empty subarray is allowed; its sum is 0, which is divisible by any k. Return the count as a 64‑bit integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Divisible Subarrays"
WHY DOES IT MATTER?
The remainder‑hashing pattern converts a global sum condition into a local equality check, enabling O(n) solutions for many subarray‑sum problems that would otherwise require quadratic time, a skill frequently tested in interviews.
OPTIMIZATION CHALLENGE
The key insight is that (prefix[i] – prefix[j]) % k == 0 ⇔ prefix[i] % k == prefix[j] % k. By storing counts of each remainder, each new element contributes the number of previously seen equal remainders, collapsing the double loop into a single pass.
REAL-WORLD CONNECTION
Think of a circular buffer of network packets where you need to detect when the total bytes transmitted over any consecutive window equals a multiple of a bandwidth quota; tracking cumulative bytes modulo the quota lets you spot qualifying windows instantly, just like the algorithm does for array sums.
During the interview, compute the running remainder first, normalize it to a non‑negative value, and immediately add the current map count to the answer before incrementing the map – this order avoids off‑by‑one errors for subarrays that start at index 0.
COMPLEXITY AT A GLANCE
O(n)O(min(n,k))Core Theory — Why This Approach?
The problem asks for the number of contiguous subarrays whose sum is a multiple of k. A naive solution would enumerate every possible subarray, compute its sum, and check divisibility, which leads to O(n^2) time and quickly becomes infeasible for n up to 10^5 or higher. The optimal solution relies on prefix sums combined with modular arithmetic: if two prefix sums have the same remainder when divided by k, the subarray between them has a sum divisible by k because the difference of the two sums is a multiple of k. By maintaining a hash map that counts how many times each remainder has appeared, we can, in a single pass, add the current count of the remainder to the answer and then increment the map. This transforms the problem into a classic “subarray sum equals k” pattern, but with the twist that we work with remainders, turning a potentially quadratic problem into linear time.
Interview Questions on This Problem
Q1How would you modify the solution if k could be zero, i.e., you need subarrays whose sum is exactly zero?
When k is zero, the modulo trick is undefined. Instead, you count subarrays whose prefix sum equals a previous prefix sum (remainder concept becomes exact equality). Use a hash map of prefix sums to frequencies and add the current frequency to the answer each time the same sum reappears.
Q2Explain why using a plain array of size k for counting remainders can be unsafe when k is large or negative.
A plain array assumes k is a small positive integer and that remainders are in [0,k‑1]. If k is large (e.g., 10^9) the array would be memory‑prohibitive, and if k is negative the modulo operation yields negative remainders in many languages. Using a hash map avoids both issues because it stores only observed remainders.
Q3In a distributed system processing a stream of numbers, how could you compute the count of divisible subarrays without storing the entire array?
You can maintain only the running prefix sum modulo k and a hash map of remainder frequencies on each node. Each incoming element updates the prefix sum, contributes to the global count using the current remainder frequency, and updates the map. This constant‑space per node approach works because the answer depends solely on prefix‑sum remainders, not on the full data history.
Examples
Input
nums = [4,5,0,-2,-3,1], k = 5
Output
7
Explanation: Prefix sums: 0,4,9,9,7,4,5 → modulo 5: 0,4,4,4,2,4,0. Frequencies of each remainder: 0→2, 2→1, 4→4. For each remainder r, choose any two positions with the same r to form a subarray; number of pairs = C(freq,2). Thus C(2,2)=1, C(1,2)=0, C(4,2)=6. Total = 1+6=7.
Input
nums = [1,2,3,4,5], k = 3
Output
7
Explanation: Running sum modulo 3 yields: 0,1,0,0,1,0. Frequencies: 0→4, 1→2, 2→0. Pairs: C(4,2)=6 for remainder 0 and C(2,2)=1 for remainder 1. Sum = 7 subarrays whose sum is divisible by 3.
Input
nums = [-1,2,-3,4,-5,6], k = 4
Output
3
Explanation: Prefix sums modulo 4: 0,3,1,2,2,1,3. Frequencies: 0→1, 1→2, 2→2, 3→2. Pairs: C(1,2)=0, C(2,2)=1 for each of remainders 1, 2, 3. Total = 3 valid subarrays.
Constraints
- 1 <= nums.length <= 100000
- 1 <= k <= 10^9
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Use a hash map of prefix‑sum remainders; for each element, add the current remainder's frequency to the answer and then increment that frequency, achieving O(n) time.
Brute Force Approach
Enumerate all O(n^2) subarrays, compute each sum, and check if sum % k == 0.
Verified Code Solutions
function countDivisibleSubarrays(nums, k) {
const freq = new Map();
freq.set(0, 1); // empty subarray
let prefix = 0;
let ans = 0;
for(const x of nums){
prefix = (prefix + x) % k;
if(prefix < 0) prefix += k;
const cnt = freq.get(prefix) || 0;
ans += cnt;
freq.set(prefix, cnt + 1);
}
return ans;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++]||0;
const nums = data.slice(idx, idx+n); idx+=n;
const k = data[idx]||0;
console.log(countDivisibleSubarrays(nums, k));#include <bits/stdc++.h>
using namespace std;
long long countDivisibleSubarrays(const vector<int>& nums, long k) {
unordered_map<long long,long long> freq;
freq.reserve(nums.size()*2);
long long prefix = 0;
long long ans = 0;
freq[0] = 1; // empty subarray
for(int x: nums){
prefix = (prefix + x) % k;
if(prefix < 0) prefix += k;
ans += freq[prefix];
++freq[prefix];
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
long k; cin>>k;
cout<<countDivisibleSubarrays(nums,k);
return 0;
}import java.util.*;
public class Main {
public static long countDivisibleSubarrays(int[] nums, long k) {
Map<Long, Long> freq = new HashMap<>();
freq.put(0L, 1L); // empty subarray
long prefix = 0;
long ans = 0;
for (int x : nums) {
prefix = (prefix + x) % k;
if (prefix < 0) prefix += k;
long cnt = freq.getOrDefault(prefix, 0L);
ans += cnt;
freq.put(prefix, cnt + 1);
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.hasNextInt() ? sc.nextInt() : 0;
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
long k = sc.hasNextLong() ? sc.nextLong() : 0L;
System.out.println(countDivisibleSubarrays(nums, k));
sc.close();
}
}import sys
from collections import defaultdict
def countDivisibleSubarrays(nums, k):
freq = defaultdict(int)
freq[0] = 1 # empty subarray
prefix = 0
ans = 0
for x in nums:
prefix = (prefix + x) % k
if prefix < 0:
prefix += k
ans += freq[prefix]
freq[prefix] += 1
return ans
def main():
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
return
n = data[0]
nums = data[1:1+n]
k = data[1+n]
print(countDivisibleSubarrays(nums, k))
if __name__ == "__main__":
main()function countDivisibleSubarrays(nums, k) {
const freq = new Map();
freq.set(0, 1); // empty subarray
let prefix = 0;
let ans = 0;
for(const x of nums){
prefix = (prefix + x) % k;
if(prefix < 0) prefix += k;
const cnt = freq.get(prefix) || 0;
ans += cnt;
freq.set(prefix, cnt + 1);
}
return ans;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++]||0;
const nums = data.slice(idx, idx+n); idx+=n;
const k = data[idx]||0;
console.log(countDivisibleSubarrays(nums, k));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.