Medium

Count of Interesting Subarrays

LAB

Return the number of subarrays where the count of values with value mod modulo equal to k has count mod modulo equal to k.

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    2,
    4
  ],
  "modulo": 2,
  "k": 1
}

Output
3

FUNCTION SHAPE

nums: intArraymodulo: intk: int→int

SOLUTION NOTE

This is exactly the same question as before, the wording is just confusing. Transform each element to a boolean value if it is congruent to k % mod. Now a subarray sum of k % mod means that subarray is 'interesting'.

Reveal reference solution +

pythonREFERENCE

def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
    nums = [num % modulo == k for num in nums]
    return self.subarraySum(nums, modulo, k)

def subarraySum(self, nums: List[int], mod: int, k: int) -> int:
    prev_sum = Counter({0:1})  # size mod
    n, prefix_sum, res = len(nums), 0, 0
    for i in range(n):
        prefix_sum += nums[i]

        if (prefix_sum - k) % mod in prev_sum:
            res += prev_sum[(prefix_sum - k) % mod]

        prev_sum[prefix_sum % mod] += 1  # mod here!

    return res

TimeO(n)

SpaceO(min(n, mod))

Open on LeetCode ↗