Skip to content

2440. Create Components With Same Value 👍

  • Time: $O(|\sqrt{\Sigma\texttt{nums[i]}}| \cdot n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
    const int n = nums.size();
    const int sum = accumulate(begin(nums), end(nums), 0);
    vector<vector<int>> graph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    for (int i = n; i > 1; --i)
      // split the tree into i parts, i.e., delete (i - 1) edges
      if (sum % i == 0 && dfs(nums, graph, 0, sum / i, vector<bool>(n)) == 0)
        return i - 1;

    return 0;
  }

 private:
  static constexpr int kMax = 1'000'000'000;

  // Returns the sum of the subtree rooted at u minus the sum of the deleted
  // subtrees.
  int dfs(const vector<int>& nums, const vector<vector<int>>& graph, int u,
          int target, vector<bool>&& seen) {
    int sum = nums[u];
    seen[u] = true;

    for (const int v : graph[u]) {
      if (seen[v])
        continue;
      sum += dfs(nums, graph, v, target, move(seen));
      if (sum > target)
        return kMax;
    }

    // Delete the tree that has sum == target
    if (sum == target)
      return 0;
    return sum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public int componentValue(int[] nums, int[][] edges) {
    final int n = nums.length;
    final int sum = Arrays.stream(nums).sum();
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < graph.length; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    for (int i = n; i > 1; --i)
      // split the tree into i parts, i.e., delete (i - 1) edges
      if (sum % i == 0 && dfs(nums, graph, 0, sum / i, new boolean[n]) == 0)
        return i - 1;

    return 0;
  }

  private static final int kMax = 1_000_000_000;

  // Returns the sum of the subtree rooted at u minus the sum of the deleted subtrees.
  private int dfs(int[] nums, List<Integer>[] graph, int u, int target, boolean[] seen) {
    int sum = nums[u];
    seen[u] = true;

    for (final int v : graph[u]) {
      if (seen[v])
        continue;
      sum += dfs(nums, graph, v, target, seen);
      if (sum > target)
        return kMax;
    }

    // Delete the tree that has sum == target
    if (sum == target)
      return 0;
    return sum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
    kMax = 1_000_000_000
    n = len(nums)
    summ = sum(nums)
    graph = [[] for _ in range(n)]

    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)

    # Returns the sum of the subtree rooted at u minus the sum of the deleted subtrees.
    def dfs(u: int, target: int, seen: Set[bool]) -> int:
      summ = nums[u]
      seen.add(u)

      for v in graph[u]:
        if v in seen:
          continue
        summ += dfs(v, target, seen)
        if summ > target:
          return kMax

      # Delete the tree that has sum == target
      if summ == target:
        return 0
      return summ

    for i in range(n, 1, -1):
      # split the tree into i parts, i.e., delete (i - 1) edges
      if summ % i == 0 and dfs(0, summ // i, set()) == 0:
        return i - 1

    return 0