K Divisible Elements Subarrays — LeetCode 2261 Python Solution

The problem

Given an integer array nums and two integers k and p, return the number of distinct subarrays, which have at most k elements that are divisible by p. Two arrays nums1 and nums2 are said to be distinct if: They are of different lengths, or There exists at least one index i where nums1[i] != nums2[i].

Example

Input

nums = [2,3,3,2,2], k = 2, p = 2

Output

11

Explanation

The elements at indices 0, 3, and 4 are divisible by p = 2.

Python solution

class Solution:
    def countDistinct(self, nums: List[int], k: int, p: int) -> int:
        s = set()
        n = len(nums)
        base1, base2 = 131, 13331
        mod1, mod2 = 10**9 + 7, 10**9 + 9
        for i in range(n):
            h1 = h2 = cnt = 0
            for j in range(i, n):
                cnt += nums[j] % p == 0
                if cnt > k:
                    break
                h1 = (h1 * base1 + nums[j]) % mod1
                h2 = (h2 * base2 + nums[j]) % mod2
                s.add(h1 << 32 | h2)
        return len(s)

Complexity

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 2261. K Divisible Elements Subarrays is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems