Count of Interesting Subarrays

Leetcode Problem:

• Count of Interesting Subarrays

Summary

• This problem requires finding the count of subarrays that satisfy a certain condition based on the modulo and k.

Approach

• The solution uses a sliding window approach and a hashmap to keep track of the prefix sum and the count of interesting subarrays.

Complexity

• O(n)

Explanation

• The solution initializes a hashmap to store the prefix sum and its count
• It then iterates over the array, updating the prefix sum and the count of interesting subarrays
• The count of interesting subarrays is updated by adding the count of subarrays that end at the current position and have a prefix sum that satisfies the condition
• The solution returns the total count of interesting subarrays.

Solution Code:

class Solution {
public:
    long long countInterestingSubarrays(vector& nums, int modulo, int k) {
        int n = nums.size();
        unordered_map cnt;
        long long res = 0;
        int prefix = 0;
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            prefix += nums[i] % modulo == k;
            res += cnt[(prefix - k + modulo) % modulo];
            cnt[prefix % modulo]++;
        }
        return res;
    }
};