FastPrep
Problem

Minimum Town Sum Difference

Learn this problem
Google logoGoogleFULLTIMEOA
See Google hiring insights

Problem statement

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.

Function

minTownsDiff(n: int, towns: int[], roads: int[][]) → int

Examples

Example 1

n = 2towns = [10,20]roads = [[1,2]]return = 10

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

Example 2

n = 5towns = [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
checking account