53. Subarray Sums Divisible by K

🔗 LeetCode Problem: 974. Subarray Sums Divisible by K
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Prefix Sum

Problem Statement

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.

Example 1:

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], [-2, -3], [4, 5, 0, -2, -3, 1, 6]

Example 2:

Input: nums = [5], k = 9
Output: 0

Constraints: - 1 <= nums.length <= 3 × 10^4 - -10^4 <= nums[i] <= 10^4 - 2 <= k <= 10^4

---

🎨 Visual Understanding

The Problem Visualized

nums = [4, 5, 0, -2, -3, 1], k = 5

Subarrays divisible by 5:
[4, 5, 0, -2, -3, 1] → sum = 5, 5 % 5 = 0 ✓
[5] → sum = 5, 5 % 5 = 0 ✓
[5, 0] → sum = 5, 5 % 5 = 0 ✓
[5, 0, -2, -3] → sum = 0, 0 % 5 = 0 ✓
[0] → sum = 0, 0 % 5 = 0 ✓
[-2, -3] → sum = -5, -5 % 5 = 0 ✓
[4, 5, 0, -2, -3, 1] → sum = 5, 5 % 5 = 0 ✓

Total count: 7

🚨 CRITICAL INSIGHT - This Problem Combines #50 and #52!

This problem is the PERFECT combination of: - Problem #50: Divisibility check (use modulo) - Problem #52: Count subarrays (track frequency)

From Problem #50 (Continuous Subarray Sum):
  ✓ Use modulo arithmetic
  ✓ Same remainder = divisible difference
  ✓ Track remainders in HashMap

From Problem #52 (Subarray Sum Equals K):
  ✓ Count ALL valid subarrays (not just check existence)
  ✓ Track FREQUENCY (not just first occurrence)
  ✓ Add frequency to count

Combination:
  ✓ Track remainder FREQUENCY
  ✓ Same remainder = subarray divisible by k
  ✓ Each occurrence = one valid subarray

Key Observation: Use Modulo with Frequency

For subarray from index i+1 to j to be divisible by k:
  (prefixSum[j] - prefixSum[i]) % k = 0

Which means:
  prefixSum[j] % k = prefixSum[i] % k

Mathematical property:
  (a - b) % k = 0  ⟺  a % k = b % k

So we need to:
  Count how many times each remainder appears!

The Insight: Count Remainder Frequencies

nums = [4, 5, 0, -2, -3, 1], k = 5

Calculate prefix sums and remainders:

Index:  -1   0   1   2   3    4    5
Sum:     0   4   9   9   7    4    5
Mod 5:   0   4   4   4   2    4    0
         ↑       ↑   ↑        ↑    ↑
       Same!   Same! Same!  Same! Same!

Remainder 0 appears at: -1, 5 (2 times)
Remainder 4 appears at: 0, 1, 2, 4 (4 times)
Remainder 2 appears at: 3 (1 time)

Count pairs with same remainder:
  Remainder 0: C(2,2) = 1 pair
  Remainder 4: C(4,2) = 6 pairs
  Remainder 2: C(1,2) = 0 pairs

Total: 1 + 6 + 0 = 7 ✓

But we calculate this incrementally with HashMap!

🚨 CRITICAL: Handling Negative Remainders in Java

Java's modulo with negative numbers can give negative results!

In Java:
  -5 % 3 = -2 (not 1!)
  -7 % 5 = -2 (not 3!)

But we need positive remainders:
  -5 % 3 should be 1 (to match with 4 % 3 = 1)
  -7 % 5 should be 3 (to match with 8 % 5 = 3)

Solution:
  remainder = ((sum % k) + k) % k

Example:
  sum = -7, k = 5
  -7 % 5 = -2
  (-2 + 5) % 5 = 3 % 5 = 3 ✓

This ensures remainder is always in range [0, k-1]

Why This Works - Mathematical Proof

If (prefixSum[j] - prefixSum[i]) % k = 0:
  Then subarray from i+1 to j is divisible by k ✓

Modulo property:
  (a - b) % k = 0
  ⟺ a % k = b % k

At position j:
  remainder = prefixSum[j] % k

Count: How many times have we seen this remainder before?
  Each occurrence = one valid subarray ending at j!

Why frequency?
  If remainder 4 appeared 3 times before:
    3 different starting positions
    All end at current position
    = 3 subarrays divisible by k!

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all subarrays:
1. For each starting position i
2. For each ending position j
3. Calculate sum of subarray [i, j]
4. If sum % k == 0, increment count

Implementation

public int subarraysDivByK(int[] nums, int k) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum % k == 0) {
                count++;
            }
        }
    }

    return count;
}

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - only variables

---

🎯 Approach 2: Prefix Sum Array

Better Approach 💡

Core Logic:

Use prefix sum to get any subarray sum in O(1):

1. Build prefix sum array
2. Check all pairs (i, j)
3. If (prefixSum[j] - prefixSum[i]) % k = 0, increment count

Key insight:
  Difference divisible by k means same remainder

Implementation

public int subarraysDivByK(int[] nums, int k) {
    int n = nums.length;
    int count = 0;

    // Build prefix sum array
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // Check all pairs
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int diff = prefixSum[j] - prefixSum[i];
            if (diff % k == 0) {
                count++;
            }
        }
    }

    return count;
}

⏰ Time: O(n²) - checking all pairs
💾 Space: O(n) - prefix sum array

---

✅ Approach 3: HashMap with Remainder Frequency (Optimal)

The Ultimate Optimization 💡

Core Logic:

Combine concepts from problems #50 and #52:

From #50: Use modulo arithmetic
From #52: Track frequency

Key insight:
  If prefixSum[j] % k = prefixSum[i] % k
  Then (prefixSum[j] - prefixSum[i]) % k = 0

Algorithm:
1. Track running sum modulo k
2. Store FREQUENCY of each remainder
3. When same remainder seen: add its frequency to count
4. Update frequency in map

Visual Explanation:

nums = [4, 5, 0, -2, -3, 1], k = 5

Running sum with remainder frequency:

map = {0: 1}  // Initialize
sum = 0, count = 0

Index 0: nums[0] = 4
  sum = 4
  remainder = 4 % 5 = 4
  count += map.getOrDefault(4, 0) = 0
  map.put(4, 1)
  map = {0: 1, 4: 1}

Index 1: nums[1] = 5
  sum = 9
  remainder = 9 % 5 = 4
  count += map.getOrDefault(4, 0) = 1
  count = 1 (found [5])
  map.put(4, 2)
  map = {0: 1, 4: 2}

Index 2: nums[2] = 0
  sum = 9
  remainder = 9 % 5 = 4
  count += map.getOrDefault(4, 0) = 2
  count = 1 + 2 = 3 (found [5,0] and [4,5,0])
  map.put(4, 3)
  map = {0: 1, 4: 3}

Index 3: nums[3] = -2
  sum = 7
  remainder = 7 % 5 = 2
  count += map.getOrDefault(2, 0) = 0
  map.put(2, 1)
  map = {0: 1, 4: 3, 2: 1}

Index 4: nums[4] = -3
  sum = 4
  remainder = 4 % 5 = 4
  count += map.getOrDefault(4, 0) = 3
  count = 3 + 3 = 6
  map.put(4, 4)
  map = {0: 1, 4: 4, 2: 1}

Index 5: nums[5] = 1
  sum = 5
  remainder = 5 % 5 = 0
  count += map.getOrDefault(0, 0) = 1
  count = 6 + 1 = 7
  map.put(0, 2)
  map = {0: 2, 4: 4, 2: 1}

Total count: 7 ✓

Implementation

public int subarraysDivByK(int[] nums, int k) {
    // Map: remainder -> frequency
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: remainder 0 appears once
    map.put(0, 1);

    int sum = 0;
    int count = 0;

    for (int num : nums) {
        sum += num;

        // Calculate remainder (handle negative)
        int remainder = ((sum % k) + k) % k;

        // Add frequency of this remainder
        count += map.getOrDefault(remainder, 0);

        // Update frequency
        map.put(remainder, map.getOrDefault(remainder, 0) + 1);
    }

    return count;
}

⏰ Time: O(n) - single pass
💾 Space: O(k) - at most k different remainders (0 to k-1)

---

🔍 Step-by-Step Execution

Approach 2 (Prefix Sum Array): nums = [2, 3, -1], k = 3

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [2, 3, -1], k = 3
n = 3


STEP 1: Build Prefix Sum Array
═══════════════════════════════════════════════════════════════════

prefixSum[0] = 0

i=0: nums[0] = 2
  prefixSum[1] = 0 + 2 = 2

i=1: nums[1] = 3
  prefixSum[2] = 2 + 3 = 5

i=2: nums[2] = -1
  prefixSum[3] = 5 + (-1) = 4

Final prefixSum array:
  Index:  0  1  2  3
  Prefix: 0  2  5  4


STEP 2: Check All Pairs for Divisibility
═══════════════════════════════════════════════════════════════════

i=0: prefixSum[0] = 0
───────────────────────────────────────────────────────────────────
  j=1: diff = 2 - 0 = 2, 2 % 3 = 2 ≠ 0 ✗
  j=2: diff = 5 - 0 = 5, 5 % 3 = 2 ≠ 0 ✗
  j=3: diff = 4 - 0 = 4, 4 % 3 = 1 ≠ 0 ✗

i=1: prefixSum[1] = 2
───────────────────────────────────────────────────────────────────
  j=2: diff = 5 - 2 = 3, 3 % 3 = 0 ✓
       count = 1
       Subarray [3] from index 1

  j=3: diff = 4 - 2 = 2, 2 % 3 = 2 ≠ 0 ✗

i=2: prefixSum[2] = 5
───────────────────────────────────────────────────────────────────
  j=3: diff = 4 - 5 = -1, -1 % 3 = -1 ≠ 0 ✗


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 1
═══════════════════════════════════════════════════════════════════

Valid subarray: [3] with sum 3

---

Approach 3 (HashMap): nums = [4, 5, 0, -2, -3, 1], k = 5

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [4, 5, 0, -2, -3, 1], k = 5
map = {0: 1}
sum = 0
count = 0


Index 0: nums[0] = 4
═══════════════════════════════════════════════════════════════════
sum = 0 + 4 = 4

Calculate remainder:
  4 % 5 = 4
  remainder = 4

Check map for remainder 4: NOT found
  count += 0 = 0

Update map:
  map.put(4, 1)
  map = {0: 1, 4: 1}

count = 0


Index 1: nums[1] = 5
═══════════════════════════════════════════════════════════════════
sum = 4 + 5 = 9

Calculate remainder:
  9 % 5 = 4
  remainder = 4

Check map for remainder 4: FOUND with frequency 1!
  count += 1 = 1

  🔑 Found subarray [5] from index 1-1

Update map:
  map.put(4, 2)
  map = {0: 1, 4: 2}

count = 1


Index 2: nums[2] = 0
═══════════════════════════════════════════════════════════════════
sum = 9 + 0 = 9

Calculate remainder:
  9 % 5 = 4
  remainder = 4

Check map for remainder 4: FOUND with frequency 2!
  count += 2 = 3

  🔑 Found 2 subarrays ending at index 2:
     1. [5, 0] from index 1-2
     2. [4, 5, 0] from index 0-2

Update map:
  map.put(4, 3)
  map = {0: 1, 4: 3}

count = 3


Index 3: nums[3] = -2
═══════════════════════════════════════════════════════════════════
sum = 9 + (-2) = 7

Calculate remainder:
  7 % 5 = 2
  remainder = 2

Check map for remainder 2: NOT found
  count += 0 = 3

Update map:
  map.put(2, 1)
  map = {0: 1, 4: 3, 2: 1}

count = 3


Index 4: nums[4] = -3
═══════════════════════════════════════════════════════════════════
sum = 7 + (-3) = 4

Calculate remainder:
  4 % 5 = 4
  remainder = 4

Check map for remainder 4: FOUND with frequency 3!
  count += 3 = 6

  🔑 Found 3 subarrays ending at index 4:
     1. [-2, -3] from index 3-4
     2. [0, -2, -3] from index 2-4
     3. [5, 0, -2, -3] from index 1-4

Update map:
  map.put(4, 4)
  map = {0: 1, 4: 4, 2: 1}

count = 6


Index 5: nums[5] = 1
═══════════════════════════════════════════════════════════════════
sum = 4 + 1 = 5

Calculate remainder:
  5 % 5 = 0
  remainder = 0

Check map for remainder 0: FOUND with frequency 1!
  count += 1 = 7

  🔑 Found subarray from start to index 5:
     [4, 5, 0, -2, -3, 1]

Update map:
  map.put(0, 2)
  map = {0: 2, 4: 4, 2: 1}

count = 7


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 7
═══════════════════════════════════════════════════════════════════

All valid subarrays with sum divisible by 5:
  1. [5] from index 1
  2. [5, 0] from indices 1-2
  3. [4, 5, 0] from indices 0-2
  4. [-2, -3] from indices 3-4
  5. [0, -2, -3] from indices 2-4
  6. [5, 0, -2, -3] from indices 1-4
  7. [4, 5, 0, -2, -3, 1] from indices 0-5

---

Approach 3 (HashMap) - CRITICAL: Negative Remainder Example

nums = [3, -4, 2], k = 3

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [3, -4, 2], k = 3
map = {0: 1}
sum = 0
count = 0


Index 0: nums[0] = 3
═══════════════════════════════════════════════════════════════════
sum = 3

WITHOUT proper handling:
  remainder = 3 % 3 = 0

WITH proper handling:
  remainder = ((3 % 3) + 3) % 3 = (0 + 3) % 3 = 0 ✓

count += map.get(0) = 1
count = 1 (subarray [3])

map = {0: 2}


Index 1: nums[1] = -4
═══════════════════════════════════════════════════════════════════
sum = 3 + (-4) = -1

🚨 CRITICAL: Negative sum!

WITHOUT proper handling:
  remainder = -1 % 3 = -1 (negative!)
  This is WRONG! Remainder should be in [0, k-1]

WITH proper handling:
  remainder = ((-1 % 3) + 3) % 3
            = (-1 + 3) % 3
            = 2 % 3
            = 2 ✓

Now remainder is positive!

count += map.getOrDefault(2, 0) = 0
map.put(2, 1)
map = {0: 2, 2: 1}


Index 2: nums[2] = 2
═══════════════════════════════════════════════════════════════════
sum = -1 + 2 = 1

remainder = ((1 % 3) + 3) % 3 = (1 + 3) % 3 = 1

count += map.getOrDefault(1, 0) = 0
map.put(1, 1)
map = {0: 2, 2: 1, 1: 1}


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 1
═══════════════════════════════════════════════════════════════════

🚨 KEY INSIGHT:
═══════════════════════════════════════════════════════════════════

Formula: remainder = ((sum % k) + k) % k

This ensures remainder is ALWAYS in range [0, k-1]

Examples:
  sum = 7, k = 5:  ((7 % 5) + 5) % 5 = (2 + 5) % 5 = 2
  sum = -7, k = 5: ((-7 % 5) + 5) % 5 = (-2 + 5) % 5 = 3
  sum = -1, k = 3: ((-1 % 3) + 3) % 3 = (-1 + 3) % 3 = 2

Without this, negative sums give negative remainders,
which breaks the HashMap logic!

---

🔍 Edge Cases

Case 1: Single element divisible
Input: nums = [5], k = 5
Output: 1

Case 2: No valid subarray
Input: nums = [1, 2, 3], k = 7
Output: 0

Case 3: All zeros
Input: nums = [0, 0, 0], k = 3
Output: 6
Explanation: All subarrays are divisible by any k

Case 4: Negative numbers
Input: nums = [-1, 2, 9], k = 2
Output: 2
Explanation: [-1, 2] and [9] (9 % 2 = 1, but [-1,2,9] sum=10)
Actually: [2] and [-1, 2, 9]

Case 5: k = 1
Input: nums = [1, 2, 3], k = 1
Output: 6
Explanation: All subarrays (any sum % 1 = 0)

Case 6: Large negative remainder
Input: nums = [-5, -3], k = 3
Output: 1
Explanation: [-5, -3] sum = -8, -8 % 3 needs proper handling

Case 7: Multiple same remainders
Input: nums = [2, 3, 5], k = 5
Output: 1
Explanation: [2, 3] has sum 5

---

Common Mistakes

Mistake 1: Not initializing map with {0: 1}
❌ Wrong: 
    Map<Integer, Integer> map = new HashMap<>();
✓ Right: 
    map.put(0, 1);
Reason: Handles subarrays from start that are divisible by k

Mistake 2: Not handling negative remainders
❌ Wrong: 
    int remainder = sum % k;
✓ Right: 
    int remainder = ((sum % k) + k) % k;
Reason: Java's % can return negative values

Mistake 3: Only storing existence (not frequency)
❌ Wrong: 
    map.put(remainder, 1);  // Always 1
✓ Right: 
    map.put(remainder, map.getOrDefault(remainder, 0) + 1);
Reason: Need to count ALL occurrences

Mistake 4: Checking if sum % k == 0 directly
❌ Wrong: 
    if (sum % k == 0) count++;
✓ Right: 
    count += map.getOrDefault(remainder, 0);
Reason: Misses subarrays not starting from index 0

Mistake 5: Using map.get() without checking
❌ Wrong: 
    count += map.get(remainder);  // NullPointerException
✓ Right: 
    count += map.getOrDefault(remainder, 0);
Reason: Remainder may not exist in map

Mistake 6: Forgetting that 0 % k = 0
❌ Wrong: 
    Only count non-zero remainders
✓ Right: 
    Initialize with {0: 1} and count remainder 0
Reason: Subarrays with sum 0 or multiples of k are valid

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Prefix Sum Array
  Time: O(n²)
  Space: O(n)
  Use: Learning step

Approach 3: HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(k)
  Use: Optimal solution

🔑 The Core Insight

🚨 THIS PROBLEM = Problem #50 + Problem #52
═══════════════════════════════════════════════════════════════

From Problem #50 (Continuous Subarray Sum):
───────────────────────────────────────────────────────────────
✓ Use modulo arithmetic
✓ Same remainder means divisible difference
✓ Track remainders in HashMap
✓ Handle negative remainders

From Problem #52 (Subarray Sum Equals K):
───────────────────────────────────────────────────────────────
✓ COUNT all valid subarrays (not just check existence)
✓ Track FREQUENCY (not just first occurrence)
✓ Add frequency to count
✓ Each occurrence = one subarray

Combined Algorithm:
═══════════════════════════════════════════════════════════════

1. Track running sum modulo k
2. Store FREQUENCY of each remainder
3. When same remainder seen: add frequency to count
4. Update frequency in map

Mathematical Relationship:
═══════════════════════════════════════════════════════════════

Goal: Count subarrays with sum divisible by k

If (prefixSum[j] - prefixSum[i]) % k = 0:
  Then prefixSum[j] % k = prefixSum[i] % k

At position j:
  remainder = prefixSum[j] % k

Count all previous occurrences of this remainder!
  Each occurrence = one valid subarray

Why Frequency Matters:
═══════════════════════════════════════════════════════════════

If remainder 4 appeared 3 times:
  3 different starting positions
  All end at current position
  All create subarrays divisible by k
  = 3 valid subarrays!

🚨 CRITICAL: Negative Remainder Handling
═══════════════════════════════════════════════════════════════

Java's modulo with negative numbers:
  -7 % 5 = -2 (not 3!)
  -1 % 3 = -1 (not 2!)

Solution:
  remainder = ((sum % k) + k) % k

This ensures: 0 <= remainder < k

Example:
  sum = -7, k = 5
  Wrong: -7 % 5 = -2
  Right: ((-7 % 5) + 5) % 5 = (-2 + 5) % 5 = 3 ✓

Algorithm Pattern:
═══════════════════════════════════════════════════════════════

1. Initialize: map = {0: 1}, sum = 0, count = 0
2. For each element:
   a. sum += element
   b. remainder = ((sum % k) + k) % k
   c. count += map.getOrDefault(remainder, 0)
   d. map.put(remainder, map.getOrDefault(remainder, 0) + 1)
3. Return count

Space Complexity:
═══════════════════════════════════════════════════════════════

O(k) not O(n)!

Why? Only k possible remainders: 0, 1, 2, ..., k-1

This is better than O(n) when k < n!

🎯 Pattern Recognition

Problem Evolution: The Trilogy!
┌──────────────────────────────────────────────────────────┐
│ #50: Continuous Subarray Sum (divisible by k)          │
│      Track: remainder → first index                     │
│      Return: boolean (exists or not)                    │
│      Formula: ((sum % k) + k) % k                       │
│                                                          │
│ #52: Subarray Sum Equals K                             │
│      Track: sum → frequency                             │
│      Return: int (count)                                │
│      Formula: count occurrences of (sum - k)            │
│                                                          │
│ #53: Subarray Sums Divisible by K (THIS PROBLEM)       │
│      Track: remainder → FREQUENCY ⭐                     │
│      Return: int (count)                                │
│      Formula: ((sum % k) + k) % k + frequency tracking  │
│      = Problem #50 + Problem #52! 🎯                    │
└──────────────────────────────────────────────────────────┘

Key Differences:
═══════════════════════════════════════════════════════════

#50 vs #53:
  #50: Check if exists → store first index → return boolean
  #53: Count all → store frequency → return count

#52 vs #53:
  #52: Exact sum = k → no modulo needed
  #53: Divisible by k → use modulo + handle negatives

All three use prefix sum + HashMap!
Just different tracking strategies!

🧠 Interview Strategy

Step 1: "Count subarrays with sum divisible by k"
Step 2: "Recognize: Problem #50 + Problem #52 combined!"
Step 3: "Use modulo like #50, frequency like #52"
Step 4: "Key formula: ((sum % k) + k) % k"
Step 5: "Track remainder frequency in HashMap"
Step 6: "Same remainder = divisible subarray"
Step 7: "Add frequency to count, then update map"
Step 8: "O(n) time, O(k) space"

Key Points to Mention:
- Combines concepts from two previous problems
- Modulo arithmetic for divisibility
- Frequency tracking for counting
- Handle negative remainders: ((sum % k) + k) % k
- HashMap stores remainder → frequency
- Initialize {0: 1} for edge cases
- Count before updating map
- Space is O(k) not O(n)
- Single pass solution

Why Modulo Property?
"If two prefix sums have the same remainder when divided by k,
their difference is divisible by k. This is the same property
from problem #50. But unlike #50 which checks existence, here
I need to COUNT all such subarrays, so I track frequency like
in problem #52."

Why Handle Negative?
"Java's modulo operator can return negative values for negative
numbers. Since I'm using remainders as HashMap keys, I need them
in the range [0, k-1]. The formula ((sum % k) + k) % k ensures
this by adding k and taking modulo again."

This perfectly combines two fundamental patterns! 🏆

---

📝 Quick Revision Notes

🎯 Core Concept:

🚨 CRITICAL: This is Problem #50 + Problem #52 combined! Use modulo (from #50) + frequency (from #52). Must handle negative remainders: ((sum % k) + k) % k

The Perfect Combination:

From #50: Modulo arithmetic, same remainder = divisible
From #52: Frequency tracking, count all occurrences

Result: Track remainder FREQUENCY!

Why Handle Negatives?

Java: -7 % 5 = -2 (wrong for our use!)
Need: -7 % 5 = 3 (to match with other remainders)

Formula: ((sum % k) + k) % k
Ensures: 0 <= remainder < k

⚡ Quick Implementation:

import java.util.HashMap;

class Test {
  public int subarraysDivByK(int[] a, int k) {
    int res = 0;
    int len = a.length;
    // // Approach 1 - using prefixsum alone O(N2)
    // // Any subarray sum => s = prefix[j] - prefix[i] => s % k = 0
    // // (prefix[j] - prefix[i]) % k = 0
    // // prefix[j] % k = prefix[i] % k
    // // Derive prefixSum array
    // int[] prefixSum = new int[len + 1];
    // for(int i = 1; i <= len; i++) {
    //   prefixSum[i] = prefixSum[i - 1] + a[i - 1];
    // }
    // // Count how many instances prefix[j] % k = prefix[i] % k
    // for(int i = 0; i <= len; i++) {
    //   for(int j = i + 1; j <= len; j++) {
    //     int psj = prefixSum[j] % k;
    //     // Gotcha - below is exlusively for -ve modulus
    //     // -1 % 3 = -1. Ideally, should be -1 + 3 = 2 to be in [0, k-1]
    //     if(psj < 0) {
    //       psj = psj + k;
    //     }
    //     int psi = prefixSum[i] % k;
    //     if(psi < 0) {
    //       psi = psi + k;
    //     }
    //     if(psj % k == psi % k) {
    //       res++;
    //     }
    //   }
    // }

    // // Approach 2 - using prefixsum and hashmap
    // int[] prefixSum = new int[len + 1];
    // for(int i = 1; i <= len; i++) {
    //   prefixSum[i] = prefixSum[i - 1] + a[i - 1];
    // }
    // // Map to store reminders and their counts
    // HashMap<Integer, Integer> map = new HashMap<>();
    // // Count how many instances prefix[j] % k = prefix[i] % k
    // for(int i = 0; i <= len; i++) {      
    //   int psi = prefixSum[i] % k;
    //   // Gotcha - below is exlusively for -ve modulus
    //   // -1 % 3 = -1. Ideally, should be -1 + 3 = 2 to be in [0, k-1]
    //   if(psi < 0) {
    //     psi = psi + k;
    //   }

    //   // check if counterpart exists which we saved in our earlier loops.
    //   if(map.containsKey(psi)) {
    //     res += map.get(psi);
    //   }

    //   map.put(psi, map.getOrDefault(psi, 0) + 1);
    // }

    // Approach 3 - no need of prefixsum. Can use only runningsum (rest same)
    // If no queries, ideally runningsum itself is enough
    int sum = 0;    
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    for(int i = 0; i < len; i++) {
      sum += a[i];
      int psi = sum % k;
      if(psi < 0) {
        psi = psi + k;
      }

      // check if counterpart exists which we saved in our earlier loops.
      if(map.containsKey(psi)) {
        res += map.get(psi);
      }

      map.put(psi, map.getOrDefault(psi, 0) + 1);
    }

    return res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.subarraysDivByK(new int[] {4,5,0,-2,-3,1}, 5));
    System.out.println(t.subarraysDivByK(new int[] {5}, 9));
    System.out.println(t.subarraysDivByK(new int[] {-1, 2, 9}, 2));
  }
}

🔑 Key Insights:

• 🚨 CRITICAL: Combines #50 (modulo) + #52 (frequency)
• Pattern: Prefix sum + modulo + frequency tracking
• Formula: remainder = ((sum % k) + k) % k (MUST handle negative!)
• Why modulo: Same remainder = divisible difference
• Why frequency: Each occurrence = one valid subarray
• HashMap: Maps remainder → frequency
• Initialize: {0: 1} handles divisible from start
• Space: O(k) not O(n) - only k possible remainders!
• Count then update: Order matters!
• Time: O(n) - single pass

🎪 Memory Aid:

"#50's modulo + #52's frequency = #53! Handle negative: add k, mod again!"
Think: "Same remainder, count frequency, handle negative!"

💡 The Key Formula:

remainder = ((sum % k) + k) % k

Why add k?
  Converts negative remainder to positive

Why mod k again?
  Keeps result in range [0, k-1]

Example:
  -7 % 5 = -2
  (-2 + 5) % 5 = 3 ✓

🔥 Why This Works:

If remainder appeared 4 times:
  4 different starting positions
  All ending at current position
  All create divisible subarrays
  = 4 valid subarrays!

Add ALL frequencies = total count!

⚠️ Critical Details:

1. Initialize: map.put(0, 1)
2. Handle negative: ((sum % k) + k) % k
3. Count first: count += map.get(remainder)
4. Then update: map.put(remainder, freq + 1)
5. Space is O(k), not O(n)!
6. Track frequency, not existence/index

🎯 The Trilogy Completed:

#50: Divisible → Boolean → First Index
#52: Equals K → Count → Frequency
#53: Divisible → Count → Frequency + Modulo

All use prefix sum + HashMap!

---

Related Patterns

• Continuous Subarray Sum (LC 523) - Problem #50
• Subarray Sum Equals K (LC 560) - Problem #52
• Make Sum Divisible by P (LC 1590)
• Count Number of Nice Subarrays (LC 1248)

---

Happy practicing! 🎯