Subarray Sum Divisible By K.

#dsa #programming #cpp #productivity

🧠 Intuition:

The key insight is that:

If the difference between two prefix sums is divisible by k, then the subarray between those two indices has a sum divisible by k.

This is where modular arithmetic helps:
If prefixSum[j] % k == prefixSum[i] % k, then prefixSum[j] - prefixSum[i] is divisible by k.

🔍 Approach (Prefix Sum + HashMap):

Prefix Sum: Keep a running sum (prefixSum) while iterating through the array.

Modulo Operation: For each prefix sum, compute mod = prefixSum % k.

Normalization: Handle negative remainders by converting them into positive:if (mod < 0) mod += k;

HashMap: Use a map to store frequency of each mod value seen so far.

If the same mod has occurred before, it means a subarray ending at current index has a sum divisible by k.

Count: Increase count by the frequency of the current mod seen before.

Initialization: Start with prefixMap[0] = 1 to handle cases where a subarray from the beginning is divisible by k.

📊 Time and Space Complexity:

Metric Value Explanation
🕒 Time Complexity O(n) Single pass through array
🧠 Space Complexity O(k) Hash map stores at most k unique remainders

✅ Example:

Input:

`nums = [4, 5, 0, -2, -3, 1], k = 5
Prefix sum steps:

Prefix sum = 4 → 4 % 5 = 4

Prefix sum = 9 → 9 % 5 = 4 → Found a match (same mod as before)

Prefix sum = 9 → 9 % 5 = 4 → Another match

Prefix sum = 7 → 7 % 5 = 2

Prefix sum = 4 → 4 % 5 = 4 → More matches!

Prefix sum = 5 → 5 % 5 = 0 → New match`
Answer: 7 valid subarrays.

Code

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
      int cnt = 0, pf = 0;
      unordered_map<int, int>mp;

      mp[0] = 1;

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

        int mod = pf % k;

        if(mod < 0){
            mod += k;
        }

        if(mp.find(mod) != mp.end()){
            cnt += mp[mod];
            mp[mod]++;
        }else{
            mp[mod] = 1;
        }
      }
      return cnt;
    }
};

📁 Organized DSA Repository
I've started a DSA-in-C++ GitHub repository where all problems are sorted algorithm-wise into folders like: