K Divisible Elements Subarrays - Solution & Explanation

Problem Overview: Given an integer array nums, an integer k, and p, count the number of distinct subarrays where at most k elements are divisible by p. Two subarrays are considered the same if their sequences of values are identical.

The challenge has two parts: enforcing the constraint on divisible elements and ensuring only unique subarrays are counted. Straight enumeration works, but you must track uniqueness efficiently using hashing or a trie.

Approach 1: Brute Force with Set for Distinctions (O(n^2 * L) time, O(n^2) space)

Enumerate every possible subarray starting at index i. As you extend the subarray to the right, maintain a counter of numbers divisible by p. Once the counter exceeds k, stop extending that start index because any longer subarray will also violate the constraint. Each valid subarray is inserted into a hash set (typically as a tuple or encoded string) so duplicates are removed automatically.

This approach relies heavily on a array traversal and a hash table to track uniqueness. The main cost comes from storing and hashing subarray representations, which can take up to O(L) per insertion where L is the subarray length. Despite the quadratic enumeration, the early break when divisible elements exceed k prunes many cases.

Approach 2: Optimized Sliding Window with HashMap (O(n^2) time, O(n^2) space)

A more efficient implementation avoids repeatedly rebuilding subarray representations. Use a sliding expansion from each start index while maintaining the count of numbers divisible by p. Instead of storing raw subarrays, compute an incremental rolling hash for each extension and insert the hash into a set or hashmap.

Each time the window grows by one element, update the hash value using a polynomial rolling hash formula. This avoids copying the entire subarray and keeps insertion close to constant time. The window stops expanding once the divisible count exceeds k. Because hashes represent subarrays uniquely with very high probability, duplicates are filtered efficiently.

This approach combines enumeration with hashing techniques similar to substring problems. It leverages ideas from hash tables and structures like a trie, which can also store subarray prefixes without duplication.

Recommended for interviews: Start with the brute-force enumeration to show you understand how to enforce the k divisible constraint. Interviewers typically expect you to optimize the uniqueness check using hashing (or a trie). The optimized hashing approach demonstrates stronger algorithmic thinking and reduces overhead from repeatedly copying subarrays.