PROBLEM LINK:
Author: Akshay Venkataramani
Tester: Timothy Jeyadoss
DIFFICULTY:
Easy-Medium
PREREQUISITES:
XOR Property, Graphs, BFS/DFS
EXPLANATION:
The optimal answer can be reached, only if we perform the operation starting from the root till the leaf. Any other sequence of operations will affect previously produced answer, and hence this observation is crucial.
Hence we perform a depth-first-traversal (also known as depth-first-search (DFS)) on the tree, and if we find that a node has a value different from its target, we increment our overall answer.
We need to maintain two variables - each for odd and even heights respectively. Let us store it an array of 2 variables(named as parity in Author’s solution). Both parity[0] and parity[1] are initialized to zero.
This is essential due to the following reason :
Consider a tree with root 1 , and 3 being its granchild . In this tree, if both 1 and 3 have initialValues not equal to targetValues, performing the operation once(on node 1) is enough for node 3 to also have its value flipped(i.e., to the target value).
In the author’s solution, the height of root is set at 1 and the remaining nodes’ heights are set appropriately.
Hence, during the dfs, we check for two things :-
1) Let x be the height of the current node. if parity[x%2] == 0, it means that the current node has no effective flips in it, i.e., its current value is equal to its initial value. If initialValue[currentNode] is not equal to target[currentNode] , we incremement overall answer, and do parity[x%2]=(parity[x%2]+1)%2 . Try to understand why this step is done by yourself, using pen or paper and by constructing various trees, before moving to the next part.
- The next part should be simple, if you understood the first part well. If parity[x%2]==1, it means there’s an effective flip waiting in the currentNode. Hence, if initialValue[currentNode]==target[currentNode], the effective flip waiting to be performed on the current node is done. When we perform it, the value is no longer equal to target. Hence, we need to increment overall answer and also do
parity[x%2]=(parity[x%2]+1)%2.
Third case -> parity[x%2] == 0 and initialValue[currentNode] == target[currentNode]. Here, we needn’t do anything and leave it as such.
Fourth Case -> parity[x%2] == 1 and initialValue[currentNode] != target[currentNode]. Here, we needn’t do anything again and leave it as such. This is because, the effective flip remaining in the node, when performed, makes the values equal.
AUTHOR’S SOLUTION:
Author’s solution can be found here.
TESTER’S SOLUTION:
Tester’s solution can be found here.