The O(n) Club: Subarray Sums Divisible by K (Now with Fewer Caffeine-Induced Tears)

The O(n) Club: Subarray Sums Divisible by K (Now with Fewer Caffeine-Induced Tears)

⚡ TL;DR

Want to know how many subarrays have sums divisible by K? Sure you do, or else the interviewer will start grinding their teeth. Brute force is so slow even your coffee gets cold (O(n²)), but prefix sums plus a hash map nets you a solution faster than your caffeine crash. See for yourself:

// Java: fast logic, no espresso required
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, res = 0;
for (int n : nums) {
    sum += n;
    int rem = ((sum % k) + k) % k;
    res += map.getOrDefault(rem, 0);
    map.put(rem, map.getOrDefault(rem, 0) + 1);
}
return res;

🧠 How Devs Usually Mess This Up

If you thought “let’s just check every subarray”—congratulations, you have O(n²) intuition and probably some runtime regrets. Most folks also forget:

• Negative numbers throw mod for a loop—and Java’s mod operator is particularly petty about negatives.
• Subarrays from the start (index 0) exist—but if you forget to initialize your mod-zero count, you can kiss them goodbye.
• “Contiguous” means nobody skips the queue—no piecing together random slices. Only side-by-side elements count.

🔍 What’s Actually Going On

Imagine your bank account (or coffee supply, pick your poison) tracked over time. Every day, you note your total. If two days have the same remainder when divided by K, the sum of transactions in-between is a glorious multiple of K. It’s like time travel, except all you need is a running sum, mod math, and a trusty hash map for déjà vu remainders.

🛠️ PseudoCode

• Start with a map: Map<Integer, Integer> count = new HashMap<>(); count.put(0, 1);
• Scan the array: For each element, update running total. Find rem = ((sum % k) + k) % k; (because negative mods can ruin your day).
• Count remainders: For every previous match, add count.getOrDefault(rem, 0) to your answer—because that’s another valid subarray.
• Update your map: count.put(rem, count.getOrDefault(rem, 0) + 1);
• Spoiler: that’s it. No nested loops, no late-night debugging tears.

• Why does this wizardry work? Because matching remainders at two positions means the stuff sandwiched in-between is made of full K-sized slices. Think modular cake—every slice adds up.

💻 The Code

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int sum = 0, result = 0;
    for (int n : nums) {
        sum += n;
        int rem = ((sum % k) + k) % k;
        result += count.getOrDefault(rem, 0);
        count.put(rem, count.getOrDefault(rem, 0) + 1);
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negative numbers: Java will happily hand you negative mods. Always fix with ((x % k) + k) % k or join the “off-by-one” club.
• Forget to count subarrays starting at zero? Don’t. map.put(0, 1) is non-negotiable.
• Brute force sadness: O(n²) solutions fail hard with big arrays. Interviewers can smell them a mile off.
• Time/Space Complexity: O(n) time; O(k) space. No bloat, no drama.

🧠 Interviewer Brain-Tattoo

“Every time a prefix sum mod K repeats, a valid subarray earns its wings. Don’t overthink it—hash, mod, and move on.”