1
class Solution {
2
 public:
3
  int subarraysDivByK(vector<int> &nums, int k) {
4
    // take an ans variable
5
    int ans = 0;
6
    // initialize a map of int, int and insert {0,1} as 0 occurs first time for
7
    // sum
8
    unordered_map<int, int> mapp;
9
    mapp.insert({0, 1});
10
    // initialize presum = 0 and remainder rem = 0 which will be used in further
11
    // calculations
12
    int presum = 0;
13

14
    int rem = 0;
15

16
    // Logic
17
    /*
18
        1. We will traverse the entire given array/vector.
19
        2. While traversing we will add the element in our presum, i.e presum +=
20
       nums[i] .
21
        3. Now we will do the % of presum and k and store it in rem that we have
22
       created.
23
        4. We need to take care of negative value of rem. If it is < 0, then we
24
       will add k to the remainder to make it positive.
25
        5. Now we will check if rem already exist in the map. If it exist then
26
       we will add it's frequency to ans variable and then increment rem's value
27
       in map, i.e. mapp[rem]++, else we will add it in the map.
28
        6. At last we will return ans.
29
    */
30

31
    for (int i = 0; i < nums.size(); i++) {
32
      presum += nums[i];
33
      rem = presum % k;
34
      if (rem < 0) rem += k;
35

36
      if (mapp.find(rem) != mapp.end()) {
37
        ans += mapp[rem];
38
        mapp[rem]++;
39
      } else {
40
        mapp.insert({rem, 1});
41
      }
42
    }
43
    return ans;
44
  }
45
};