1
class Solution {
2
  public int subarraysDivByK(int[] nums, int k) {
3
    HashMap<Integer, Integer> map = new HashMap<>();
4
    int count = 0;
5
    int sum = 0;
6
    for (int i = 0; i < nums.length; i++) {
7
      sum += nums[i];
8
      int rem = sum % k;
9
      if (rem < 0) {
10
        rem = rem + k; // -4%3 == -1 and 2 both bec -4 = 3(-1) +(-1) = 3(-2) + 2
11
      }
12

13
      if (rem == 0) {
14
        count++;
15
      }
16
      if (map.containsKey(rem)) {
17
        count += map.get(rem);
18
      }
19

20
      map.put(rem, map.getOrDefault(rem, 0) + 1);
21
    }
22
    return count;
23
  }
24
}