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:
i where nums1[i] != nums2[i].A subarray is defined as a non-empty contiguous sequence of elements in an array.
Example 1:
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. 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 Explanation: 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 <= 2001 <= nums[i], p <= 2001 <= k <= nums.lengthFollow up:
Can you solve this problem in O(n2) time complexity?
To solve #2261 K Divisible Elements Subarrays, the goal is to count the number of distinct subarrays where the number of elements divisible by p does not exceed k. A practical strategy is to enumerate all subarrays starting from each index while maintaining a counter of elements divisible by p. If the count exceeds k, the expansion for that starting index stops early.
Because the problem requires counting only unique subarrays, we must track previously seen sequences. This can be done using a rolling hash stored in a hash set or by inserting elements into a Trie structure as the subarray grows. These techniques help efficiently identify duplicate subarrays without storing entire sequences repeatedly.
For each starting index, extend the subarray to the right while updating the divisible count and computing the rolling hash (or traversing the Trie). This leads to roughly O(n²) subarray exploration with efficient uniqueness checks. The space usage depends on how many unique subarrays are stored.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumeration + Hash Set with Rolling Hash | O(n^2) | O(n^2) |
| Enumeration + Trie for unique subarrays | O(n^2) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Enumerate all subarrays and find the ones that satisfy all the conditions.
Use any suitable method to hash the subarrays to avoid duplicates.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Rolling hash allows you to represent a subarray with a compact numeric value that can be updated efficiently as the subarray grows. This helps detect duplicate subarrays quickly without storing the entire sequence each time.
Yes, problems involving subarray enumeration, hashing, and uniqueness checks are common in technical interviews. This question tests understanding of arrays, hashing techniques, and efficient duplicate detection strategies.
A hash set combined with a rolling hash is commonly used to track distinct subarrays efficiently. Alternatively, a Trie can represent all explored subarrays and naturally avoid duplicates while expanding sequences.
A common approach is to enumerate all subarrays while counting how many elements are divisible by p. If the count exceeds k, stop expanding that subarray. Use a rolling hash or Trie to store unique subarrays and avoid duplicates.