Count of Interesting Subarrays — LeetCode 2845 Python Solution

The problem

You are given a 0-indexed integer array nums, an integer modulo, and an integer k. Your task is to find the count of subarrays that are interesting.

Example

Input

nums = [3,2,4], modulo = 2, k = 1

Output

3

Explanation

In this example the interesting subarrays are:

Python solution

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        arr = [int(x % modulo == k) for x in nums]
        cnt = Counter()
        cnt[0] = 1
        ans = s = 0
        for x in arr:
            s += x
            ans += cnt[(s - k) % modulo]
            cnt[s % modulo] += 1
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2845. Count of Interesting Subarrays is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems