FastPrep
Problem · Tree

Minimum Flips to Match Expected Binary Values in a Tree

Learn this problem
● HardUkg logoUkgOA

Problem statement

You are given an undirected tree with tree_nodes nodes, numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node initially has a binary value (0 or 1) given by the array initial[], and an expected binary value given by the array expected[].

You can perform the following operation any number of times:

Pick a node u and flip its value along with all nodes v in the subtree of u where v % 2 == u % 2. Flipping a value means toggling between 0 and 1.

Find the minimum number of operations needed so that the final binary values match expected[].

Function

minimumFlipsToMatch(tree_nodes: int, tree_from: int[], tree_to: int[], initial: int[], expected: int[]) → int

Examples

Example 1

tree_nodes = 4tree_from = [0, 0, 1]tree_to = [1, 2, 3]initial = [1, 1, 0, 1]expected = [0, 1, 1, 0]return = 2
Pick node 0 and flip it → initial = [0, 1, 1, 1] Pick node 3 and flip it → initial = [0, 1, 1, 0] (matches expected)

Example 2

tree_nodes = 5tree_from = [0, 1, 0, 1]tree_to = [1, 2, 3, 4]initial = [1, 0, 1, 1, 0]expected = [1, 1, 0, 1, 1]return = 3
:O

More Ukg problems

drafts saved locally
public int minimumFlipsToMatch(int tree_nodes, int[] tree_from, int[] tree_to, int[] initial, int[] expected) {
  // write your code here
}
tree_nodes4
tree_from[0, 0, 1]
tree_to[1, 2, 3]
initial[1, 1, 0, 1]
expected[0, 1, 1, 0]
expected2
checking account