Maximum Number of K-Divisible Components - Practice Coding Problems

Maximum Number of K-Divisible Components - Problem

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the ith node, and an integer k.

A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by k, where the value of a connected component is the sum of the values of its nodes.

Return the maximum number of components in any valid split.

Input & Output

Example 1 — Basic Tree Split

$ Input: n = 5, edges = [[0,2],[1,2],[1,3],[1,4]], values = [1,8,1,4,4], k = 6

› Output: 2

💡 Note: We can split the tree by removing the edge between nodes 1 and 2. This creates two components: {0,2} with sum 1+1=2 (not divisible by 6), and {1,3,4} with sum 8+4+4=16 (not divisible by 6). But we can remove edges (1,3) and (1,4) to get components {0,2,1} with sum 10 (not divisible) and {3},{4} with sums 4,4. The optimal split gives us 2 components: {1,4,3} sum=16 and {0,2} sum=2, but since we need divisible sums, we get components {1,3,4} sum=16 and {0,2} sum=2. Actually, the correct split removes edge (0,2) to get {0} sum=1, {2,1,3,4} sum=17. The optimal solution finds 2 valid components.

Example 2 — Single Node

$ Input: n = 1, edges = [], values = [10], k = 5

› Output: 1

💡 Note: Single node with value 10 is divisible by 5, so we get 1 component.

Example 3 — No Valid Split

$ Input: n = 3, edges = [[0,1],[1,2]], values = [1,2,3], k = 7

› Output: 0

💡 Note: Total sum is 6, which is not divisible by 7. No matter how we split, we cannot get components with sums divisible by 7.

Constraints

1 ≤ n ≤ 3 × 10⁴
edges.length == n - 1
0 ≤ a_i, b_i < n
values.length == n
0 ≤ values[i] ≤ 10⁹
1 ≤ k ≤ 10⁹
Sum of values[i] is divisible by k

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with node values and divisor k

Find Cuts

Identify edges to remove for optimal splitting

Count Components

Maximum components with k-divisible sums

Key Takeaway

🎯 Key Insight: Use DFS to greedily cut subtrees when their sum is divisible by k - this maximizes the number of valid components

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use DFS to greedily cut subtrees when their sums are divisible by k. This maximizes the number of valid components. Best approach is DFS traversal with bottom-up sum calculation. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Edge Removals	O(2^n × n²)	O(n²)	Try all possible combinations of edge removals and check if resulting components are k-divisible
DFS with Subtree Sum Checking	O(n)	O(n)	Use DFS to traverse the tree and greedily cut edges when subtree sums are divisible by k

Brute Force - Try All Edge Removals — Algorithm Steps

Generate all possible edge removal combinations
For each combination, find connected components
Check if all component sums are divisible by k
Return maximum valid component count

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible edge removal patterns

Check Components

For each pattern, find connected components

Validate Sums

Check if all component sums are divisible by k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int n, int edges[][2], int edgeCount, int* values, int k) {
    if (n == 1) {
        return values[0] % k == 0 ? 1 : 0;
    }
    
    int maxComponents = 0;
    
    // Try all possible edge removal combinations
    for (int mask = 0; mask < (1 << edgeCount); mask++) {
        // Build adjacency matrix
        bool adj[n][n];
        memset(adj, false, sizeof(adj));
        
        for (int i = 0; i < edgeCount; i++) {
            if (!(mask & (1 << i))) { // Edge not removed
                int u = edges[i][0], v = edges[i][1];
                adj[u][v] = adj[v][u] = true;
            }
        }
        
        // Find connected components using DFS
        bool visited[n];
        memset(visited, false, sizeof(visited));
        int componentCount = 0;
        bool valid = true;
        
        for (int node = 0; node < n && valid; node++) {
            if (!visited[node]) {
                // DFS to find component
                int stack[n], top = 0;
                int component[n], compSize = 0;
                stack[top++] = node;
                
                while (top > 0) {
                    int curr = stack[--top];
                    if (!visited[curr]) {
                        visited[curr] = true;
                        component[compSize++] = curr;
                        for (int neighbor = 0; neighbor < n; neighbor++) {
                            if (adj[curr][neighbor] && !visited[neighbor]) {
                                stack[top++] = neighbor;
                            }
                        }
                    }
                }
                
                // Check if component sum is divisible by k
                long long componentSum = 0;
                for (int i = 0; i < compSize; i++) {
                    componentSum += values[component[i]];
                }
                
                if (componentSum % k != 0) {
                    valid = false;
                } else {
                    componentCount++;
                }
            }
        }
        
        if (valid && componentCount > maxComponents) {
            maxComponents = componentCount;
        }
    }
    
    return maxComponents;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified parsing for this example
    int edges[n-1][2];
    int values[n];
    int k;
    
    // Parse inputs (simplified)
    for (int i = 0; i < n-1; i++) {
        scanf("%d %d", &edges[i][0], &edges[i][1]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }
    scanf("%d", &k);
    
    printf("%d\n", solution(n, edges, n-1, values, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n²)

2^(n-1) combinations times O(n²) to check each combination

⚠ Quadratic Growth

Space Complexity

O(n²)

Store adjacency lists and visited arrays for component checking

⚠ Quadratic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Edge Removals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler