We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of K-Divisible Components

Number: 3058

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an undirected tree of n nodes (labeled 0 to n−1) with specified edges and a value on each node, we want to remove a set of edges (possibly none) such that each resulting connected component has a total value that is divisible by k. The goal is to maximize the number of connected components (which is equivalent to maximizing the number of removed edges plus one) in a valid split.

Key Insights

  • Because the whole tree’s sum is divisible by k, if a subtree’s sum itself is divisible by k, we can remove the edge connecting it to its parent to form a valid component.
  • Use a depth-first search (DFS) to compute the sum of each subtree.
  • When a non-root subtree returns a sum divisible by k, count it as a removable part and do not add its sum to the parent (this “cut” preserves the divisibility condition in both resulting components).
  • The maximum number of components is the number of successful removals plus one (for the remaining component).

Space and Time Complexity

Time Complexity: O(n) – we visit each node once in the DFS. Space Complexity: O(n) – to store the tree as an adjacency list and the recursion stack.

Solution

We use a DFS starting from an arbitrary root (here we choose node 0). For each node, we calculate the sum of its subtree. For every child, if its subtree sum is divisible by k, then the edge between the node and that child can be removed. In this case, we increment our counter and do not add that child's sum to the parent's sum (because that subtree becomes an independent valid component). Otherwise, we add the child's subtree sum to the parent's sum. Finally, the answer is the number of removals plus one (for the remaining tree component).

Key details:

  • Use an adjacency list to represent the tree.
  • Recursively compute the subtree sum.
  • When a subtree sum mod k is 0 (and the node is not the root), count it as a removable edge.
  • Final answer = (number of removals) + 1.

Code Solutions

# Python solution with line-by-line comments
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)

def maxKDivisibleComponents(n, edges, values, k):
    # Build the graph as an adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Global variable to count the number of removable edges
    removable_edges = 0
    
    # DFS function to compute the sum of subtree values
    def dfs(node, parent):
        nonlocal removable_edges
        subtree_sum = values[node]  # Start with current node's value
        for neighbor in graph[node]:
            if neighbor == parent:  # Skip the node we came from
                continue
            # Recursively compute the sum for the child subtree
            child_sum = dfs(neighbor, node)
            # If the child's subtree sum is divisible by k,
            # then we can remove the edge connecting neighbor to node.
            if child_sum % k == 0:
                removable_edges += 1  # Remove the edge: count it and do not add to parent's sum.
            else:
                subtree_sum += child_sum  # Otherwise, include it in the parent's sum.
        return subtree_sum

    total_sum = dfs(0, -1)
    # By problem constraints, total sum % k == 0, so the final split is valid.
    return removable_edges + 1

# Example usage:
n = 5
edges = [[0,2],[1,2],[1,3],[2,4]]
values = [1,8,1,4,4]
k = 6
print(maxKDivisibleComponents(n, edges, values, k))  # Expected output: 2
← Back to All Questions