#2261

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

K Divisible Elements Subarrays

Count all distinct subarrays with at most k elements divisible by p using array scanning and hash lookup techniques efficiently.

array hash table trie rolling hash hash function

Problem Statement

Given an integer array nums and two integers k and p, determine the total number of distinct subarrays where no more than k elements are divisible by p. A subarray is a continuous sequence of elements from nums.

Two subarrays are considered distinct if their sequences differ in content or order. Your task is to enumerate and count all such subarrays while ensuring duplicates are not counted more than once.

Examples

Example 1

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

Output: 11

The elements at indices 0, 3, and 4 are divisible by p = 2. The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are: [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2]. Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once. The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.

Example 2

Input: nums = [1,2,3,4], k = 4, p = 1

Output: 10

All element of nums are divisible by p = 1. Also, every subarray of nums will have at most 4 elements that are divisible by 1. Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.

Constraints

1 <= nums.length <= 200
1 <= nums[i], p <= 200
1 <= k <= nums.length

Solution Approach

Enumerate All Subarrays

Iterate over each starting index in nums and generate subarrays until the number of divisible elements exceeds k. Track the count of divisible elements as you expand each subarray.

Use Hashing to Ensure Uniqueness

Store each valid subarray in a hash set or a trie structure to prevent counting duplicates. The hash key can represent the subarray content or a rolling hash to improve speed.

Optimize with Early Termination

Stop extending a subarray once the number of divisible elements exceeds k to avoid unnecessary computations. Combine this with efficient hash checks to maintain performance for larger arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on how many subarrays are generated and hashed, potentially O(n^2) in worst-case enumeration. Space complexity depends on the storage of distinct subarrays in a hash set or trie, which can grow proportional to the number of unique subarrays.

What Interviewers Usually Probe

Focus on counting subarrays with constraints on divisible elements rather than total subarrays.
Ask about strategies to avoid counting duplicates efficiently using hashing.
Consider how to stop subarray expansion early when constraints are violated.

Common Pitfalls or Variants

Common pitfalls

Failing to count only distinct subarrays and double-counting repeated sequences.
Continuing to extend subarrays after the divisible element count exceeds k.
Using inefficient comparison methods for subarray uniqueness instead of hashing.

Follow-up variants

Count subarrays where exactly k elements are divisible by p instead of at most k.
Allow subarrays of fixed length and count those meeting the divisible constraint.
Compute the total sum of elements in subarrays with at most k divisible elements.

FAQ

What defines a distinct subarray in K Divisible Elements Subarrays?

A subarray is distinct if its sequence of elements differs from all other subarrays, even if lengths are the same. Duplicate sequences are only counted once.

How do I efficiently check uniqueness of subarrays?

Use a hash set or a trie to store subarrays. Rolling hash techniques can represent subarrays with a single numeric key, speeding up duplicate detection.

What is the best way to avoid exceeding k divisible elements?

Track the count of elements divisible by p while extending each subarray and terminate expansion once count exceeds k.

Can GhostInterview handle large arrays for this problem?

Yes, by using hash-based uniqueness checks and early termination, GhostInterview scales to arrays up to the maximum constraints efficiently.

Does the problem pattern focus on array scanning plus hash lookup?

Exactly, the main pattern is scanning all subarrays while using hash structures to record unique sequences that satisfy the divisible element constraint.

terminal

Solution

Solution 1: Enumeration + String Hashing

We can enumerate the left endpoint $i$ of the subarray, and then enumerate the right endpoint $j$ in the range $[i, n)$. During the enumeration of the right endpoint, we use double hashing to store the hash value of the subarray into a set. Finally, we return the size of the set.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Continue Practicing

#1948 delete duplicate folders in system #3042 count prefix and suffix pairs i #3045 count prefix and suffix pairs ii