2845: Count-of-Interesting-Subarrays
Medium

code
- complexity
- learnings

The key to this question is to utilise the power of prefix-sum arrays.

Example:

for [3, 2, 4, 5, 7, 2, 3], we can pre-compute values satisfying nums[i] % modulo == k
- as a result, we get the array [1, 0, 0, 1, 1, 0, 1]
however, if we want to check what the cnt is between any 2 indices, we can compute a prefix-sum array, ps_array,
- the prefix-sum array will thus be [1, 1, 1, 2, 3, 3, 4]
- then, calculate the cnt using (ps_array[j] - ps_array[i]) % modulo == k for index i and j where i < j
  - note, however, that we can rewrite this equation to (ps_array[j] - k) == ps_array[i] (mod modulo), implying that we can create a hash-map to hash the number of times ps_array[i] % modulo has appeared previously
  - that implies that we can just calculate (ps_array[j] - k) % modulo to check the previous count in the hashmap

code

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1; // for the cases, where the entire array is `cnt % modulo``
        long long counter = 0;
        long long ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            counter += (nums[i] % modulo == k);
            ans += mp[(counter + modulo - k)%modulo];
            ++mp[counter%modulo];
        }
        return ans;
    }
};

2845: Count-of-Interesting-Subarrays Medium

table of contents

code

complexity

learnings

2845: Count-of-Interesting-Subarrays
Medium