Maximum Number of K-Divisible Components

Hard
1715.

Maximum Number of K-Divisible Components

Maximum Number of K-Divisible Components is a hard coding problem on depth-first search and trees, asked in Amazon and Google interviews.

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^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a, b < n
  • values.length == n
  • 0 <= values[i] <= 10^9
  • 1 <= k <= 10^9
  • the sum of values is divisible by k
  • edges represents a valid tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} values
 * @param {number} k
 * @return {number}
 */
var maxKDivisibleComponents = function(n, edges, values, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a, b < n
  • values.length == n
  • 0 <= values[i] <= 10^9
  • 1 <= k <= 10^9
  • the sum of values is divisible by k
  • edges represents a valid tree

Hints for Maximum Number of K-Divisible Components

  1. Hint 1

    Root the tree. Cutting the edge above a node v is only allowed if the part cut off — what remains of v's subtree — is divisible by k.

  2. 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 by k too.

  3. Hint 3

    So count the subtrees whose sum is 0 mod k in one post-order pass; the root's subtree always qualifies. Keep sums modulo k to 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

  1. Get an order of the nodes from root 0 with their parents (iterative DFS or BFS).
  2. Process nodes children-first, accumulating sum[v] = (values[v] + Σ sum[child]) mod k.
  3. Whenever sum[v] == 0, count one component.
  4. 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^9 add up to nearly 2 · 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^4 nodes 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 count

Java

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