Skip to main content
Talentd

K Divisible Elements Subarrays - Solution & Explanation

MediumArrayHash TableTrieRolling Hash14 min readAsked at: Amazon, Uber, Turing
Practice this problem

Problem Statement

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].

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 <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length

 

Follow up:

Can you solve this problem in O(n2) time complexity?

Approach Overview

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.

Approach 1: Brute Force with Set for Distinctions

In this approach, we generate all possible subarrays of the input array using two nested loops. For each subarray, we count the number of elements divisible by `p`. If the count is less than or equal to `k`, we add the subarray as a tuple to a set to ensure distinctness. Finally, the size of the set gives us the required count of distinct subarrays.

This solution uses two nested loops to generate all subarrays and counts the number of elements divisible by p. A set is used to store each subarray uniquely.

Code

PythonJavaScriptC++JavaC#

Python

JavaScript

C++

Java

C#

Complexity

Time Complexity: O(n^3) due to nested loops and set operations.

Space Complexity: O(n^2) due to the storage of subarrays in the set.

Try this approach in the editor →

Approach 2: Optimized Sliding Window with HashMap

This approach optimizes the subarray generation process using a sliding window technique. We utilize a hashmap to keep track of subarray counts, efficiently managing the addition and removal of elements to/from the subarray as we slide the window.

The optimized sliding window approach generates subarrays by extending one end while counting divisible elements with adjustable starting points, skipping further extensions if conditions are not met.

Code

PythonJavaScriptC++JavaC#

Python

JavaScript

C++

Java

C#

Complexity

Time Complexity: O(n^2) since subarrays are handled more efficiently compared to the brute-force approach.

Space Complexity: O(n^2) for distinct subarray storage in sets.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

Python

Python

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Set for Distinctions

Time Complexity: O(n^3) due to nested loops and set operations.

Space Complexity: O(n^2) due to the storage of subarrays in the set.

Optimized Sliding Window with HashMap

Time Complexity: O(n^2) since subarrays are handled more efficiently compared to the brute-force approach.

Space Complexity: O(n^2) for distinct subarray storage in sets.

Enumeration + String Hashing—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Set for DistinctionsO(n^2 * L)O(n^2)Simple implementation when constraints are moderate and clarity is preferred
Optimized Sliding Window with HashMap (Rolling Hash)O(n^2)O(n^2)Best practical approach to reduce subarray copying and speed up uniqueness checks

Video Solution

K Divisible Elements Subarrays | Leetcode 2261 | Maps | Contest 291 🔥🔥 • Coding Decoded • 4,316 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K Divisible Elements Subarrays easy or hard?
K Divisible Elements Subarrays is generally rated Medium. The enumeration idea is straightforward, but handling distinct subarrays efficiently requires hashing or trie techniques, which adds algorithmic complexity.
How to solve K Divisible Elements Subarrays in O(n)?
An O(n) solution is not feasible because the number of distinct subarrays itself can reach O(n^2). The best achievable complexity enumerates subarrays with early stopping when more than k elements are divisible by p, resulting in O(n^2) time.
What is the best approach for K Divisible Elements Subarrays?
The most practical solution enumerates subarrays while tracking the count of elements divisible by p and stores each valid subarray using a rolling hash in a set. This avoids copying full subarrays and ensures uniqueness efficiently. The overall complexity is O(n^2) time and O(n^2) space.
What data structure is used in K Divisible Elements Subarrays?
The main data structures are a hash set or hashmap to store unique subarrays (often via rolling hash values). Some implementations also use a trie to store subarray prefixes without duplication, though hashing is more common in interview solutions.
What is the time complexity of K Divisible Elements Subarrays?
The optimized approach runs in O(n^2) time because every starting index may expand up to n positions. Hashing allows constant‑time uniqueness checks. Space complexity is O(n^2) in the worst case to store distinct subarray hashes.
K Divisible Elements Subarrays Python or Java solution approach?
Both Python and Java implementations follow the same idea: iterate over each start index, track how many elements are divisible by p, compute a rolling hash for the growing subarray, and insert it into a set to count unique results.
Is K Divisible Elements Subarrays asked at Google, Amazon, or Meta?
This problem reflects common interview patterns involving subarray enumeration, hashing, and constraint tracking. Variants of the problem appear in interviews at large tech companies where candidates must combine array traversal with hash‑based deduplication.

Ready to solve this problem?

Practice K Divisible Elements Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Nice Subarrays

Next

Subarray With Elements Greater Than Varying Threshold