Maximum Number of K-Divisible Components — Solution
Maximum Number of K-Divisible Components solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Number of K-Divisible Components is a hard coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Trees
- 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
An undirected tree has n nodes numbered 0 to n - 1, joined by the n - 1 edges in edges. Node i has the value values[i], and the sum of all values is divisible by the integer k.
A valid split removes some set of edges (possibly none) so that the value of every resulting component — the sum of its nodes' values — is divisible by k.
Return the maximum number of components in any valid split.
Example 1
Input: n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
Output: 2
Explanation: Remove the edge [1,2]: the components {1,3} (8 + 4 = 12) and {0,2,4} (1 + 1 + 4 = 6) are both divisible by 6.
Example 2
Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
Output: 3
Explanation: Remove [0,1] and [0,2]: {0} = 3, {1,3,4} = 6 and {2,5,6} = 9.
Example 3
Input: n = 1, edges = [], values = [0], k = 7
Output: 1
Constraints
1 <= n <= 3 * 10^4edges.length == n - 1edges[i].length == 20 <= a, b < nvalues.length == n0 <= values[i] <= 10^91 <= k <= 10^9the sum of values is divisible by kedges represents a valid tree
Hints for Maximum Number of K-Divisible Components
Hint 1
Root the tree. Cutting the edge above a node
vis only allowed if the part cut off — what remains ofv's subtree — is divisible byk.Hint 2
Work bottom-up: if a subtree's sum is divisible by
k, cutting it off never hurts, because the rest of the tree keeps a sum divisible byktoo.Hint 3
So count the subtrees whose sum is
0 mod kin one post-order pass; the root's subtree always qualifies. Keep sums modulokto avoid overflow.
How to solve Maximum Number of K-Divisible Components
A component boundary can sit above node v exactly when v's subtree sum is divisible by k: the total is divisible by k, so what is left above is divisible too. Every such subtree can be cut at once, giving one component per divisible subtree.
Approach
- Get an order of the nodes from root 0 with their parents (iterative DFS or BFS).
- Process nodes children-first, accumulating
sum[v] = (values[v] + Σ sum[child]) mod k. - Whenever
sum[v] == 0, count one component. - Return the count (the root always contributes 1).
Why it works
If v's subtree sum is divisible by k, cutting above v splits off a valid piece and leaves a remainder that is still divisible, so all such cuts can be made together; the components are then the gaps between consecutive cuts, each with sum equal to a difference of multiples of k. Conversely, any valid split only cuts above nodes whose subtree sum is divisible (the subtree is the union of complete components). So the number of divisible subtrees is the maximum.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Two remainders below
k ≤ 10^9add up to nearly2 · 10^9— use 64-bit arithmetic before taking the remainder. - Values may be 0, so a zero-valued leaf is a component on its own.
- Recursion can overflow on a path of
3 · 10^4nodes in some runtimes; an explicit order avoids it.
Reference solution
Python
from typing import List
def maxKDivisibleComponents(n: int, edges: List[List[int]], values: List[int], k: int) -> int:
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent = [-1] * n
order = [0]
seen = [False] * n
seen[0] = True
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
order.append(v)
rem = [x % k for x in values]
count = 0
for u in reversed(order):
if rem[u] == 0:
count += 1
if parent[u] >= 0:
rem[parent[u]] = (rem[parent[u]] + rem[u]) % k
return countJava
public static int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] parent = new int[n], order = new int[n];
boolean[] seen = new boolean[n];
long[] rem = new long[n];
for (int i = 0; i < n; i++) { parent[i] = -1; rem[i] = values[i] % k; }
int head = 0, tail = 0;
order[tail++] = 0;
seen[0] = true;
while (head < tail) {
int u = order[head++];
for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; order[tail++] = v; }
}
int count = 0;
for (int p = n - 1; p >= 0; p--) {
int x = order[p];
if (rem[x] == 0) count++;
if (parent[x] >= 0) rem[parent[x]] = (rem[parent[x]] + rem[x]) % k;
}
return count;
}C++
int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> parent(n, -1), order = {0};
vector<bool> seen(n, false);
vector<long long> rem(n);
for (int i = 0; i < n; i++) rem[i] = values[i] % k;
seen[0] = true;
for (size_t h = 0; h < order.size(); h++) {
int u = order[h];
for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; order.push_back(v); }
}
int count = 0;
for (int p = n - 1; p >= 0; p--) {
int x = order[p];
if (rem[x] == 0) count++;
if (parent[x] >= 0) rem[parent[x]] = (rem[parent[x]] + rem[x]) % k;
}
return count;
}JavaScript
var maxKDivisibleComponents = function(n, edges, values, k) {
var adj = [];
for (var i = 0; i < n; i++) adj.push([]);
for (var e = 0; e < edges.length; e++) { adj[edges[e][0]].push(edges[e][1]); adj[edges[e][1]].push(edges[e][0]); }
var parent = [], seen = [], rem = [];
for (var j = 0; j < n; j++) { parent.push(-1); seen.push(false); rem.push(values[j] % k); }
var order = [0];
seen[0] = true;
for (var h = 0; h < order.length; h++) {
var u = order[h];
for (var t = 0; t < adj[u].length; t++) {
var v = adj[u][t];
if (!seen[v]) { seen[v] = true; parent[v] = u; order.push(v); }
}
}
var count = 0;
for (var p = n - 1; p >= 0; p--) {
var x = order[p];
if (rem[x] === 0) count++;
if (parent[x] >= 0) rem[parent[x]] = (rem[parent[x]] + rem[x]) % k;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals