Subarray Sums Divisible by K
Mahabharata — Yudhishthira's Yagna — Counting Offerings Divisible by the Sacred Number K
यत्र-यत्र समभागः K-युक्तः सम्भवति। शेषः समानः पूर्वे चेत् — योगः K-भाज्यः निश्चितम्॥
*Wherever division into K parts is possible — where the same remainder was seen before — the sum there is certainly divisible by K.*
The Story
Before the great Rajasuya Yagna, Yudhishthira had to prepare offerings divisible by the sacred number K. Each of n successive priests would bring an offering (positive, negative, or zero). The total offering of any contiguous group of priests must be divisible by K for the group's contribution to be accepted.
"How many such contiguous groups exist?" the chief priest Dhaumya asked.
The clever approach used prefix sums and modular arithmetic.
**The key theorem:** A subarray [j+1..i] has a sum divisible by K if and only if `prefixSum[i] % K == prefixSum[j] % K`.
Proof: `sum[j+1..i] = prefixSum[i] - prefixSum[j]`. For this to be divisible by K, we need `prefixSum[i] ≡ prefixSum[j] (mod K)` — their remainders must be equal.
**Algorithm:** - Maintain a running prefix sum mod K - Store a map of `remainder → count of times seen` - For each new prefix sum, look up `currentRemainder` in the map; that count = number of valid subarrays ending here - Initialize map with `{0: 1}` (the empty prefix with remainder 0)
**Handling negative remainders in Java:** Java's `%` can return negative values for negative inputs. Normalize: `rem = ((sum % k) + k) % k`.
Dhaumya demonstrated with `nums = [4, 5, 0, -2, -3, 1]`, K = 5:
map = {0:1}
- i=0 (4): sum=4. rem=4%5=4. look for 4: map[4]=0. count+=0. map={0:1,4:1} - i=1 (5): sum=9. rem=9%5=4. look for 4: map[4]=1. count+=1 ([5] at [1..1]? Wait: map[4]=1 from prefix at i=0. Subarray [1..1]=[5], sum=5, 5%5=0≠4. Hmm. Actually [0..1]=[4,5]=9, 9%5=4. But 9 not div by 5. Wait: look for rem=4 means looking for previous prefix with SAME remainder=4, and prev was i=0. So subarray [1..1]=prefixSum[1]-prefixSum[0]=9-4=5, 5%5=0. Oh wait I'm confusing myself.
Let me retrace: count += map[currentRem]. currentRem at i=1 is 4. map[4]=1 (from i=0). This means: the previous prefix sum at i=0 had the same remainder. Subarray (i=0..i=1)=[4+5]=9, which is 9%5=4, not divisible. Wait...
Actually: we're looking for subarrays from j+1 to i where sum is divisible by K. prefixSum[i] % K == prefixSum[j] % K. Here prefixSum[1]%5 = 9%5 = 4, and we look for earlier prefixes with remainder 4. PrefixSum[0]%5=4%5=4. So subarray [1..1] = prefixSum[1]-prefixSum[0]=9-4=5. 5%5=0. YES, divisible! So it WORKS.
Let me retrace more carefully: - i=0: sum=4, rem=4%5=4. count+=map[4]=0. map={0:1,4:1} - i=1: sum=9, rem=9%5=4. count+=map[4]=1. count=1. (subarray[1..1]=5, 5%5=0 ✓). map={0:1,4:2} - i=2: sum=9, rem=4. count+=map[4]=2. count=3. map={0:1,4:3} (two subarrays ending at i=2: [2..2]=[0] (0%5=0✓), [1..2]=[5+0]=5 (5%5=0✓)) Wait: subarrays ending at i=2 with same remainder: prefixSum[1]=9 (rem 4) and prefixSum[0]=4 (rem 4). Subarray [2..2]=sum-9=0, 0%5=0 ✓ Subarray [1..2]=sum-4=5, 5%5=0 ✓ Yes, 2 subarrays, count=3 so far. - i=3: sum=7, rem=2. count+=map[2]=0. count=3. map+{2:1} - i=4: sum=4, rem=4. count+=map[4]=3. count=6. Three subarrays ending at i=4 with sum div by 5: prefixes with rem=4: at i=0(4),i=1(9),i=2(9). Subarrays from 1,2,3 to 4: [1..4]=sum-4=0✓, [2..4]=sum-9=-5✓, [3..4]=sum-9=-5✓. - i=5: sum=5, rem=0. count+=map[0]=1. count=7. map+{5:1} (but 5%5=0, so it goes into map[0]=2). Subarray [0..5]=[4+5+0-2-3+1]=5, 5%5=0 ✓
Final count: 7.
Dhaumya confirmed: seven contiguous groups of priests whose offerings sum to a multiple of 5.
"The remainder map collapses what would be O(n²) individual sum checks into O(1) lookups," Vidura observed. "Two prefix sums with the same remainder define a subarray divisible by K — modular arithmetic's version of prefix sum equality."
This is the Prefix Sum with Modular Arithmetic technique for counting subarrays divisible by K.
Dhaumya's First Instinct
Try every pair of start and end indices. Check if the subarray sum is divisible by K. O(n²) time.
public int subarraysDivByKBruteForce(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum % k == 0) count++;
}
}
return count;
}Vidura's Modular Wisdom
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> remainderCount = new HashMap<>();
remainderCount.put(0, 1); // Empty prefix has remainder 0
int count = 0;
int sum = 0;
for (int n : nums) {
sum += n;
// Normalize: Java % can be negative for negative sums
int rem = ((sum % k) + k) % k;
// Each previous prefix with same remainder forms a valid subarray
count += remainderCount.getOrDefault(rem, 0);
remainderCount.merge(rem, 1, Integer::sum);
}
return count;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().subarraysDivByK(new int[]{4,5,0,-2,-3,1}, 5)); // 7
System.out.println(new Solution().subarraysDivByK(new int[]{5}, 9)); // 0
System.out.println(new Solution().subarraysDivByK(new int[]{1,2,3,4,5}, 5)); // 4
}Step-by-Step Walkthrough
nums = [1, 2, 3, 4, 5], k = 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
map={0:1}, sum=0, count=0
n=1: sum=1, rem=1. count+=map[1]=0. map={0:1,1:1}
n=2: sum=3, rem=3. count+=map[3]=0. map={...,3:1}
n=3: sum=6, rem=1. count+=map[1]=1. count=1.
(subarray [3..3]? No: prefix at i=0 has rem=1, so subarray [1..2]=[2,3]=5, 5%5=0 ✓)
map={0:1,1:2,3:1}
n=4: sum=10, rem=0. count+=map[0]=1. count=2.
(subarray [0..3]=[1,2,3,4]=10, 10%5=0 ✓)
map={0:2,1:2,3:1}
n=5: sum=15, rem=0. count+=map[0]=2. count=4.
Two subarrays: [0..4]=[1..5]=15 ✓, [3..4]=[4,5]=9... wait 9%5≠0.
Let me recheck: rem=0 found in map at positions before: empty prefix (sum=0) and i=3 (sum=10).
Subarrays: (empty..i=4)=[0..4]=15 ✓ and (i=3+1..i=4)=[4..4] hmm...
Actually subarray from j+1 to 4: j was at i=3 position (sum=10), so subarray [4..4]=5, 5%5=0 ✓ YES!
map={0:3,1:2,3:1}
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 4
The 4 subarrays: [5], [2,3], [1,2,3,4,5], [1,2,3,4]...
Actually let's verify: [5]=5✓, [2,3]=5✓, [5]+others... [1,2,3,4]=10✓, [1,2,3,4,5]=15✓. YES, 4 subarrays.Deep Insight
**Why same remainder means divisible difference?**
If `prefixSum[i] % K == prefixSum[j] % K`, then: `prefixSum[i] = a×K + r` and `prefixSum[j] = b×K + r` for the same remainder r. `prefixSum[i] - prefixSum[j] = (a-b)×K` — perfectly divisible by K!
**The map key is the remainder (0 to K-1):** Only K possible remainders. The map has at most K entries — O(K) space, often much less than O(n) for large arrays with small K.
**Handling Java's negative modulo:** `-7 % 5 = -2` in Java (not 3). We want the true mathematical remainder 3. Fix: `((sum % k) + k) % k`. Adding k ensures non-negative, dividing by k again brings it back to [0, k-1].
**Connection to ps-1 (Subarray Sum Equals K):** - ps-1: count subarrays where `prefixSum[i] - prefixSum[j] == K` → store exact values - ps-3: count subarrays where `(prefixSum[i] - prefixSum[j]) % K == 0` → store remainders Same technique, different key: exact values vs. remainders.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All O(n²) start-end pairs checked |
| Optimal | O(n) | O(k) | Map has at most k distinct remainders |
Pattern Recognition
✅ Count subarrays with sum divisible by K ✅ Prefix sum + modular arithmetic ✅ Map stores remainder counts (not exact sums) ✅ Normalize negative remainders with `((sum%k)+k)%k` **LeetCode Trigger Phrases:** → "subarray sums divisible by k" → "count subarrays" + "divisible by" + K → "number of subarrays" + modulo + zero
Bhagavad Gita 3.10
सहयज्ञाः प्रजाः सृष्ट्वा पुरोवाच प्रजापतिः। अनेन प्रसविष्यध्वमेष वोऽस्त्विष्टकामधुक्॥
In the beginning, the Lord of creatures created humans along with yajna and said: 'By this yajna shall you prosper; may it fulfill all your desires.'
Connection: The yajna (sacred offering) must be divisible by K — the sacred number. The algorithm finds all stretches of offerings that meet this sacred divisibility. Like the cosmic cycle of yajna described in the Gita — where giving leads to receiving, and the cycle perpetuates itself — the modular arithmetic reveals a cyclical pattern: every time the running prefix sum returns to a previously seen remainder, a complete offering cycle (divisible sum) has been completed.