Count of Interesting Subarrays | Leetcode 2845

class Solution {
    #define ll long long
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        ll n = nums.size();
        ll pos=0;
        ll interesting_subarrays = 0;
        ll prefix_count = 0;

        unordered_map<ll,ll> mod_freq;
        mod_freq[0]=1;
        while(pos<n){
            if(nums[pos]%modulo==k)
                prefix_count++;
            
            prefix_count %= modulo;
            if(mod_freq.count((prefix_count-k+modulo)%modulo))
                interesting_subarrays += mod_freq[(prefix_count-k+modulo)%modulo];
            
            mod_freq[prefix_count]++;
            pos++;
        }
        return interesting_subarrays;
    }
};
/*
//JAVA
import java.util.HashMap;

class Solution {
    public long countInterestingSubarrays(int[] nums, int modulo, int k) {
        long n = nums.length;
        long pos = 0;
        long interesting_subarrays = 0;
        long prefix_count = 0;

        HashMap<Long, Long> mod_freq = new HashMap<>();
        mod_freq.put(0L, 1L);
        while (pos < n) {
            if (nums[(int)pos] % modulo == k)
                prefix_count++;
            
            prefix_count %= modulo;
            long key = (prefix_count - k + modulo) % modulo;
            if (mod_freq.containsKey(key))
                interesting_subarrays += mod_freq.get(key);
            
            mod_freq.put(prefix_count, mod_freq.getOrDefault(prefix_count, 0L) + 1);
            pos++;
        }
        return interesting_subarrays;
    }
}

#Python
from collections import defaultdict

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        n = len(nums)
        pos = 0
        interesting_subarrays = 0
        prefix_count = 0

        mod_freq = defaultdict(int)
        mod_freq[0] = 1
        while pos < n:
            if nums[pos] % modulo == k:
                prefix_count += 1
            
            prefix_count %= modulo
            key = (prefix_count - k + modulo) % modulo
            if key in mod_freq:
                interesting_subarrays += mod_freq[key]
            
            mod_freq[prefix_count] += 1
            pos += 1
        return interesting_subarrays
*/