2845. Count of Interesting Subarrays

based on 974. Subarray Sums Divisible by K

T:O(n)
S:O(k), map<remainder(0~k-1), count

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        int n = nums.size();
        int[] mod = new int[n];
        for (int i = 0; i < n; i++) {
            mod[i] = (nums.get(i)%modulo == k ? 1 : 0);
        }
        Map<Long, Long> remainderMap = new HashMap<>();
        remainderMap.put(0l, 1l);
        long result = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += mod[i];
            long remainder = sum % modulo;
            if (remainder < 0) {
                remainder += modulo;
            }

            long lookFor = remainder - k;
            if (lookFor < 0) {
                lookFor += modulo;
            }
            result += remainderMap.getOrDefault(lookFor, 0l);

            remainderMap.put(remainder, remainderMap.getOrDefault(remainder, 0l)+1);
            

        }
        
        return result;
    }
}

/**
nums[i] % m == k, get cnt

  [1,0,1,1]
0 1  1 2 3



cnt % m = k

nums[i] % m == 1
3,2,4

  1, 0, 0
0 1. 1  1


[11,12,21,31]
10
1

5

*/