K Divisible Elements Subarrays — Problem & Solution
K Divisible Elements Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
K Divisible Elements Subarrays is a medium coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Enumeration, Trie
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and two integers k and p, return the number of distinct non-empty contiguous subarrays that contain at most k elements divisible by p.
Two subarrays are the same when they have the same length and the same values in the same order — where they occur in nums does not matter. For example, in [3,1,3] the two single-element subarrays [3] count once.
Example 1
Input: nums = [4,2,3,3], k = 1, p = 2
Output: 6
Explanation: `[4]`, `[2]`, `[2,3]`, `[2,3,3]`, `[3]` and `[3,3]`. Any subarray holding both 4 and 2 has two even elements.
Example 2
Input: nums = [1,1,1], k = 1, p = 5
Output: 3
Explanation: Nothing is divisible by 5, so all subarrays qualify, but only `[1]`, `[1,1]` and `[1,1,1]` are distinct.
Example 3
Input: nums = [6,3,6], k = 2, p = 3
Output: 4
Explanation: `[6]`, `[3]`, `[6,3]` and `[3,6]`; the whole array has three multiples of 3.
Constraints
1 <= nums.length <= 2001 <= nums[i], p <= 2001 <= k <= nums.length
Follow-up: Can you solve it in O(n^2) time?
Hints for K Divisible Elements Subarrays
Hint 1
There are only about
n^2 / 2subarrays. For each start index, extend the end until the count of multiples ofpexceedsk— after that, longer ones fail too.Hint 2
The hard part is deduplication. Storing every subarray as a string costs O(n^3) in total.
Hint 3
Insert the subarrays that start at
iinto a trie, one value per edge, while you extend them. A subarray is new exactly when its last step creates a new trie node.
How to solve K Divisible Elements Subarrays
All subarrays starting at index i are prefixes of one another, so they are exactly the nodes along one path of a trie keyed by values. Counting newly created trie nodes counts distinct subarrays in O(n^2).
Approach
- Create a trie with an empty root.
- For each start
i: setnode = rootandcnt = 0. - For
j = i, i+1, …: ifnums[j] % p == 0, incrementcnt; ifcnt > k, stop extending this start. - Follow (or create) the child of
nodelabellednums[j]. Creating it means the subarraynums[i..j]has never been seen — add 1 to the answer. Movenodeto that child.
Why it works
Each trie node at depth d stands for exactly one sequence of d values (the labels on its root path). Every valid subarray is inserted, and a node is created only the first time its sequence appears, so the number of created nodes equals the number of distinct valid subarrays. Stopping once cnt > k is safe because any extension keeps or increases the count.
Complexity
- Time —
O(n^2) - Space —
O(n^2)
Pitfalls
- Deduplicate by contents, not by position —
[3]at index 0 and index 2 is one subarray. - Joining values into a string key without a separator makes
[1,12]collide with[11,2]. - The divisibility count restarts for every start index.
Reference solution
Python
from typing import List
def countDistinct(nums: List[int], k: int, p: int) -> int:
children = [{}]
ans = 0
n = len(nums)
for i in range(n):
node = 0
cnt = 0
for j in range(i, n):
v = nums[j]
if v % p == 0:
cnt += 1
if cnt > k:
break
nxt = children[node].get(v)
if nxt is None:
nxt = len(children)
children.append({})
children[node][v] = nxt
ans += 1
node = nxt
return ansJava
public static int countDistinct(int[] nums, int k, int p) {
Map<Integer, Integer> child = new HashMap<>();
int nodes = 1, ans = 0;
for (int i = 0; i < nums.length; i++) {
int node = 0, cnt = 0;
for (int j = i; j < nums.length; j++) {
if (nums[j] % p == 0) cnt++;
if (cnt > k) break;
int key = node * 201 + nums[j];
Integer nxt = child.get(key);
if (nxt == null) {
nxt = nodes++;
child.put(key, nxt);
ans++;
}
node = nxt;
}
}
return ans;
}C++
int countDistinct(vector<int>& nums, int k, int p) {
unordered_map<long long, int> child;
int nodes = 1, ans = 0, n = nums.size();
for (int i = 0; i < n; i++) {
int node = 0, cnt = 0;
for (int j = i; j < n; j++) {
if (nums[j] % p == 0) cnt++;
if (cnt > k) break;
long long key = (long long) node * 201 + nums[j];
auto it = child.find(key);
if (it == child.end()) {
child[key] = nodes;
node = nodes++;
ans++;
} else {
node = it->second;
}
}
}
return ans;
}JavaScript
var countDistinct = function(nums, k, p) {
// the whole trie in one map: key node * 201 + value -> child id
var child = new Map();
var nodes = 1, ans = 0;
for (var i = 0; i < nums.length; i++) {
var node = 0, cnt = 0;
for (var j = i; j < nums.length; j++) {
if (nums[j] % p === 0) cnt++;
if (cnt > k) break;
var key = node * 201 + nums[j];
var nxt = child.get(key);
if (nxt === undefined) {
nxt = nodes++;
child.set(key, nxt);
ans++;
}
node = nxt;
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets