Maximum Number of K-Divisible Components

Maximum Number of K-Divisible Components

What is this problem about?

The Maximum Number of K-Divisible Components coding problem gives you a tree of n nodes, each with a value. You can remove any edges from the tree to split it into components. A component is "k-divisible" if the sum of its node values is divisible by k. Find the maximum number of k-divisible components you can create by removing edges.

Why is this asked in interviews?

Amazon and Google include this problem because it requires a DFS-based greedy observation on trees: when traversing a rooted tree, a subtree can be "cut off" (the edge to its parent removed) if and only if the subtree's total sum is divisible by k. This is a clean tree DP insight that rewards candidates who think recursively.

Algorithmic pattern used

DFS with greedy cutting: Root the tree at node 0. Perform a post-order DFS. For each node, compute the subtree sum modulo k. If the subtree sum mod k equals 0, this subtree is k-divisible — cut it off (increment count, return 0 to parent so the parent doesn't double-count). Otherwise, return the subtree sum mod k to the parent to accumulate. The initial count is 1 (the whole tree itself, if the total sum is divisible by k). Time: O(n).

Example explanation

Tree: 0-1, 0-2, 1-3. Values: [1, 2, 3, 4]. k=5.

• Total sum = 10 divisible by 5 → whole tree is one valid component.
• DFS from 0: node 3 → sum=4. 4%5=4≠0, return 4 to node 1. Node 1: 2+4=6, 6%5=1≠0, return 1 to node 0. Node 2: 3%5=3≠0, return 3. Node 0: 1+1+3=5, 5%5=0 → cut! Count=1.
• But wait, count starts at 0, each cut (subtree sum=0 mod k) adds 1. The root's component always counts. Let me recount: only the root component (entire tree) has sum divisible by 5. Count=1.

Common mistakes candidates make

• Counting individual node values modulo k: Only full subtree sums matter, not individual values.
• Not returning 0 to parent after cutting: Failing to zero out a cut subtree's contribution makes the parent accumulate the full subtree sum.
• Not initializing count to 0 vs 1: Count starts at 0; each zero-mod-k subtree (including root) increments by 1.

Interview preparation tip

For the Depth-First Search Tree interview pattern, the "cut subtree if sum is divisible by k" insight generalizes to many tree partition problems. The key: returning 0 to the parent after a cut is what makes the greedy work — it ensures the parent doesn't mix the cut subtree's sum into its own. Practice on similar tree component problems.