33-Subarray-Divisible-by-K.md

Subarray Divisible by K

Problem Link

https://leetcode.com/problems/subarray-sums-divisible-by-k/

---

Pattern

• Prefix Sum
• Modulo

---

Approach

Track prefix sum % k; repeated modulos indicate subarray divisible by k.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;
        for (int n : nums) {
            sum += n;
            int mod = ((sum % k) + k) % k;
            count += map.getOrDefault(mod, 0);
            map.put(mod, map.getOrDefault(mod, 0) + 1);
        }
        return count;
    }
}