FastPrep
Problem

Minimum Town Sum Difference

FULLTIMEOA
See Google online assessment and hiring insights

You are given a tree with n nodes numbered from 1 to n and n - 1 bidirectional edges. Node i + 1 has towns[i] towns.

Delete exactly one edge. This splits the tree into two connected components.

Return the minimum possible absolute difference between the total number of towns in the two resulting components.

Examples
01 · Example 1
n = 2
towns = [10,20]
roads = [[1,2]]
return = 10

Deleting the only edge creates components with sums 10 and 20, so the difference is 10.

02 · Example 2
n = 5
towns = [1,2,3,4,5]
roads = [[1,2],[1,3],[3,4],[3,5]]
return = 5

Deleting edge [1,3] gives component sums 12 and 3, difference 9. Deleting edge [3,5] gives sums 5 and 10, difference 5, which is minimum.

Constraints
  • 1 <= n <= 10^5
  • towns.length == n
  • 1 <= towns[i] <= 10^4
  • roads.length == n - 1
  • roads forms a tree.
More Google problems
drafts saved locally
public int minTownsDiff(int n, int[] towns, int[][] roads) {
  // write your code here
}
n2
towns[10,20]
roads[[1,2]]
expected10
sign in to submit