2845. Count of Interesting Subarrays

Time: O(n)

Space: O(k)

Intuition

Count interesting subarrays where count of elements with val%modulo==k satisfies count%modulo==k. Prefix count + hashmap.

Algorithm

1prefix[i] = count of elements in nums[0..i-1] with val%modulo==k.
2For each j: need prefix[j] - prefix[i] satisfies (cnt%modulo==k). Use hashmap of prefix[i]%modulo.

Common Pitfalls

•Standard prefix sum modulo trick. Map prefix_mod -> count. Answer += map[(prefix[j]-k+modulo)%modulo].

2845.cs

// Approach: Prefix count of (interesting mod k); for each right find lefts where diff ≡ m (mod k).
// Time: O(n) Space: O(k)

public class Solution
{
    public long CountInterestingSubarrays(IList<int> nums, int modulo, int k)
    {
        long ans = 0;
        int prefix = 0; // (number of nums[i] % modulo == k so far) % modulo
        Dictionary<int, int> prefixCount = new Dictionary<int, int>();
        prefixCount[0] = 1;

        foreach (var num in nums)
        {
            if (num % modulo == k)
                prefix = (prefix + 1) % modulo;
            ans += prefixCount.GetValueOrDefault((prefix - k + modulo) % modulo, 0);
            if (prefixCount.ContainsKey(prefix))
                prefixCount[prefix]++;
            else
                prefixCount[prefix] = 1;
        }

        return ans;
    }
}

Was this solution helpful?