Problem Breakdown
We need to count how many contiguous subarrays within array A have a sum that is perfectly divisible by integer K.
Inputs & Outputs:
- Input: An integer list
A, and an integer divisorK. - Output: A single integer representing the total count of valid subarrays.
Constraints Analysis:
- Array length up to 30,000 (). This immediately rules out solutions (checking every pair), pushing us toward .
- Values can be negative ().
Kis positive and .
Tricky Edge Cases:
- Negative Numbers: Subarray sums involving negatives must still satisfy divisibility. In Python, the modulo operator
%handles negatives consistently for a positive divisor (e.g.,-1 % 5 == 4). We rely on this property to group remainders correctly regardless of sign. - Zero Remainder at Start: If the prefix sum itself is divisible by
K, that counts as one subarray starting from index 0. Our hash map initialization must account for a “virtual” prefix sum of 0 before processing any elements.
Intuition
A naive approach would iterate through all possible start and end indices, calculate the sum for each window, and check divisibility. This is or worse due to repeated summation (), which will Time Out (TLE) given N = 30,000.
Key Insight: We can use Prefix Sums. Let be the sum of elements from index 0 to . The sum of a subarray between indices and is .
For this difference to be divisible by K:
This implies:
In other words, if two prefix sums have the same remainder when divided by K, then any subarray between them has a sum divisible by K. We don’t need to know the actual values of , just their remainders. If we encounter a specific remainder multiple times in our traversal, each previous occurrence forms a valid pair with the current one.
Approach
- Initialize a hash map (dictionary) called
remainder_countsto store how many times each prefix sum remainder has been seen so far. - Crucial Step: Before processing any elements, initialize
remainder_counts[0] = 1. This handles the case where a subarray starting from index 0 is divisible by K (since implies ). - Initialize
current_sumto 0 andtotal_countto 0. - Iterate through each number in array
A:- Update
current_sum. - Calculate the remainder:
rem = current_sum % K. (Note: In Python,%with a positive divisor returns a result in[0, K-1], handling negative inputs correctly).
- Update
- Check if this
remexists in our map. If it does, add its frequency tototal_count. This is because every previous occurrence of the same remainder forms a valid subarray ending at current index. - Increment the count for this specific
remin the map. - Return
total_count.
Complexity Analysis
- Time Complexity: , where is the length of array
A. We traverse the list once; dictionary lookups and updates are amortized . - Space Complexity: . The hash map stores at most one entry for each possible remainder from 0 to . Since remainders cannot exceed
K, the space is bounded byK. In practice, it’s limited by both array length and divisor size.
Solution
def subarraysDivByK(A: list[int], K: int) -> int:
# Map to store frequency of prefix sum remainders.
# Initialize with {0: 1} because a prefix sum divisible by K (remainder 0)
# implies the subarray from start is valid, effectively treating P[-1] = 0.
remainder_counts = {0: 1}
current_sum = 0
total_count = 0
for num in A:
current_sum += num
# Calculate remainder. Python's % operator handles negatives correctly
# relative to a positive divisor (e.g., -5 % 3 -> 1).
rem = current_sum % K
# If this remainder has been seen before, it means there are existing
# prefix sums with the same modulo value. Each previous occurrence forms
# a valid subarray ending at the current index.
if rem in remainder_counts:
total_count += remainder_counts[rem]
# Update frequency of this remainder for future iterations
remainder_counts[rem] = remainder_counts.get(rem, 0) + 1
return total_count
# Example usage matching problem description
if __name__ == "__main__":
A = [4,5,0,-2,-3,1]
K = 5
print(subarraysDivByK(A, K)) # Output: 7
Edge Cases Handled
- Negative Array Elements: The modulo operation in Python normalizes negative sums into the range
[0, K-1], ensuring consistent bucketing for remainders regardless of sign. - Subarrays Starting at Index 0: By initializing
remainder_counts[0] = 1before the loop, we correctly count cases where the running sum itself is divisible byK. - All Zeros or All Divisible Sums: The logic naturally accumulates counts based on frequency of remainders (e.g., if all sums are multiples of K, remainder 0 will increment in every step).