Minimize operations to convert each node of N-ary Tree from initial[i] to final[i] by flipping current node subtree in alternate fashion
Given an N-ary Tree consisting of N nodes valued from [0, N – 1] and two binary arrays initial[] and final[] of size N such that initial[i] represents the value assigned to the node i, the task is to find the minimum number of operations required to convert each value of nodes initial[i] to final[i] by flipping the value of the node, its grandchildren, and so on in an alternate fashion till leaf nodes.
Examples:
Input: N = 3, edges = {{1, 2}, {1, 3}}, initial[] = {1, 1, 0}, final[] = {0, 1, 1}
1(1)
/ \
2(1) 3(0)
Output: 2
Explanation:
Operation 1: Pick the node 1 and flips its initial values. After this operation initial[] = {0, 1, 0} and final[] = {0, 1, 1}.
Operation 2: Pick the node 3 and flips its initial values. After this operation initial[] = {0, 1, 1} and final[] = {0, 1, 1}.
Therefore, print 2 as the minimum number of operations.Input: N = 1, edges = [], initial[] = {0}, final[] = {1}
Output: 1
Approach: The given problem can be solved by performing the DFS Traversal on the given Tree and update the value of nodes in the array initial[] in an alternate fashion. Follow the steps below to solve this problem:
- Initialize a variable, say total as 0 to store the count of operations required.
- Perform DFS Traversal while keeping the track of two boolean variables (initially as false) which will only change when a flip occurs and perform the following steps:
- Mark the current node as the visited node.
- If the value of Bitwise XOR of the initial value of the current node, the final value of the current node, and the current boolean variable is non-zero, then flip the current boolean variable and increment the value of the total by 1.
- Traverse all the unvisited children of the current node, and recursively call for the DFS Traversal for the child node.
- After completing the above steps, print the value of the total as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include "bits/stdc++.h" using namespace std; // Function to add an edges in graph void addEdges(vector< int > adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Function to perform the DFS of graph // recursively from a given vertex u void DFSUtil( int u, vector< int > adj[], vector< bool >& visited, bool foo, bool foo1, int initial[], int final[], int & ans) { visited[u] = true ; // Check for the condition for the // flipping of node's initial value if ((initial[u - 1] ^ foo) ^ final[u - 1] == true ) { ans++; foo ^= 1; } // Traverse all the children of the // current source node u for ( int i = 0; i < adj[u].size(); i++) { // Swap foo and foo1 signifies // there is change of level if (visited[adj[u][i]] == false ) DFSUtil(adj[u][i], adj, visited, foo1, foo, initial, final, ans); } } // Function to perform the DFSUtil() // for all the unvisited vertices int DFS(vector< int > adj[], int V, int initial[], int final[]) { int total = 0; vector< bool > visited(V, false ); // Traverse the given set of nodes for ( int u = 1; u <= 1; u++) { // If the current node is // unvisited if (visited[u] == false ) DFSUtil(u, adj, visited, 0, 0, initial, final, total); } // Print the number of operations cout << total; } // Function to count the number of // flips required to change initial // node values to final node value void countOperations( int N, int initial[], int final[], int Edges[][2]) { // Create adjacency list vector< int > adj[N + 1]; // Add the given edges for ( int i = 0; i < N - 1; i++) { addEdges(adj, Edges[i][0], Edges[i][1]); } // DFS Traversal DFS(adj, N + 1, initial, final); } // Driver Code int main() { int N = 3; int Edges[][2] = { { 1, 2 }, { 1, 3 } }; int initial[] = { 1, 1, 0 }; int final[] = { 0, 1, 1 }; countOperations(N, initial, final, Edges); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Create adjacency list static int N = 3 ; static Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>(); static Vector<Boolean> visited; static int ans; // Function to add an edges in graph static void addEdges( int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // Function to perform the DFS of graph // recursively from a given vertex u static void DFSUtil( int u, boolean foo, boolean foo1, boolean [] initial, boolean [] finall) { visited.set(u, true ); // Check for the condition for the // flipping of node's initial value if ((initial[u - 1 ] ^ foo) ^ finall[u - 1 ] == true ) { ans+= 1 ; foo ^= true ; } // Traverse all the children of the // current source node u for ( int i = 0 ; i < adj.get(u).size(); i++) { // Swap foo and foo1 signifies // there is change of level if (visited.get(adj.get(u).get(i)) == false ) DFSUtil(adj.get(u).get(i), foo1, foo, initial, finall); } } // Function to perform the DFSUtil() // for all the unvisited vertices static void DFS( int V, boolean [] initial, boolean [] finall) { ans = 0 ; visited = new Vector<Boolean>(); for ( int i = 0 ; i < V; i++) { visited.add( false ); } // Traverse the given set of nodes for ( int u = 1 ; u <= 1 ; u++) { // If the current node is // unvisited if (visited.get(u) == false ) DFSUtil(u, false , false , initial, finall); } // Print the number of operations System.out.print(ans); } // Function to count the number of // flips required to change initial // node values to final node value static void countOperations( int N, boolean [] initial, boolean [] finall, int [][] Edges) { // Add the given edges for ( int i = 0 ; i < N - 1 ; i++) { addEdges(Edges[i][ 0 ], Edges[i][ 1 ]); } // DFS Traversal DFS(N + 1 , initial, finall); } // Driver code public static void main(String[] args) { for ( int i = 0 ; i < N + 1 ; i++) { adj.add( new Vector<Integer>()); } int [][] Edges = { { 1 , 2 }, { 1 , 3 } }; boolean [] initial = { true , true , false }; boolean [] finall = { false , true , true }; countOperations(N, initial, finall, Edges); } } // This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program for the above approach # Create adjacency list N = 3 adj = [] for i in range (N + 1 ): adj.append([]) visited = [] ans = 0 # Function to add an edges in graph def addEdges(u, v): global adj adj[u].append(v) adj[v].append(u) # Function to perform the DFS of graph # recursively from a given vertex u def DFSUtil(u, foo, foo1, initial, finall): global visited, ans, adj visited[u] = True # Check for the condition for the # flipping of node's initial value if ((initial[u - 1 ] ^ foo) ^ finall[u - 1 ] = = True ): ans + = 1 foo ^ = True # Traverse all the children of the # current source node u for i in range ( len (adj[u])): # Swap foo and foo1 signifies # there is change of level if (visited[adj[u][i]] = = False ): DFSUtil(adj[u][i], foo1, foo, initial, finall) # Function to perform the DFSUtil() # for all the unvisited vertices def DFS(V, initial, finall): global ans, visited ans = 0 visited = [ False ] * V # Traverse the given set of nodes for u in range ( 1 , 2 ): # If the current node is # unvisited if (visited[u] = = False ): DFSUtil(u, 0 , 0 , initial, finall) # Print the number of operations print (ans) # Function to count the number of # flips required to change initial # node values to final node value def countOperations(N, initial, finall, Edges): # Add the given edges for i in range (N - 1 ): addEdges(Edges[i][ 0 ], Edges[i][ 1 ]) # DFS Traversal DFS(N + 1 , initial, finall) Edges = [ [ 1 , 2 ], [ 1 , 3 ] ] initial = [ True , True , False ] finall = [ False , True , True ] countOperations(N, initial, finall, Edges) # This code is contributed by rameshtravel07. |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Create adjacency list static int N = 3; static List<List< int >> adj = new List<List< int >>(); static List< bool > visited; static int ans; // Function to add an edges in graph static void addEdges( int u, int v) { adj[u].Add(v); adj[v].Add(u); } // Function to perform the DFS of graph // recursively from a given vertex u static void DFSUtil( int u, bool foo, bool foo1, bool [] initial, bool [] finall) { visited[u] = true ; // Check for the condition for the // flipping of node's initial value if ((initial[u - 1] ^ foo) ^ finall[u - 1] == true ) { ans+=1; foo ^= true ; } // Traverse all the children of the // current source node u for ( int i = 0; i < adj[u].Count; i++) { // Swap foo and foo1 signifies // there is change of level if (visited[adj[u][i]] == false ) DFSUtil(adj[u][i], foo1, foo, initial, finall); } } // Function to perform the DFSUtil() // for all the unvisited vertices static void DFS( int V, bool [] initial, bool [] finall) { ans = 0; visited = new List< bool >(); for ( int i = 0; i < V; i++) { visited.Add( false ); } // Traverse the given set of nodes for ( int u = 1; u <= 1; u++) { // If the current node is // unvisited if (visited[u] == false ) DFSUtil(u, false , false , initial, finall); } // Print the number of operations Console.Write(ans); } // Function to count the number of // flips required to change initial // node values to final node value static void countOperations( int N, bool [] initial, bool [] finall, int [,] Edges) { // Add the given edges for ( int i = 0; i < N - 1; i++) { addEdges(Edges[i,0], Edges[i,1]); } // DFS Traversal DFS(N + 1, initial, finall); } static void Main() { for ( int i = 0; i < N + 1; i++) { adj.Add( new List< int >()); } int [,] Edges = { {1, 2}, {1, 3} }; bool [] initial = { true , true , false }; bool [] finall = { false , true , true }; countOperations(N, initial, finall, Edges); } } // This code is contributed by mukesh07. |
Javascript
<script> // Javascript program for the above approach // Create adjacency list let N = 3; let adj = []; for (let i = 0; i < N + 1; i++) { adj.push([]); } let visited; let ans; // Function to add an edges in graph function addEdges(u, v) { adj[u].push(v); adj[v].push(u); } // Function to perform the DFS of graph // recursively from a given vertex u function DFSUtil(u, foo, foo1, initial, finall) { visited[u] = true ; // Check for the condition for the // flipping of node's initial value if ((initial[u - 1] ^ foo) ^ finall[u - 1] == true ) { ans+=1; foo ^= true ; } // Traverse all the children of the // current source node u for (let i = 0; i < adj[u].length; i++) { // Swap foo and foo1 signifies // there is change of level if (visited[adj[u][i]] == false ) DFSUtil(adj[u][i], foo1, foo, initial, finall); } } // Function to perform the DFSUtil() // for all the unvisited vertices function DFS(V, initial, finall) { ans = 0; visited = new Array(V); visited.fill( false ); // Traverse the given set of nodes for (let u = 1; u <= 1; u++) { // If the current node is // unvisited if (visited[u] == false ) DFSUtil(u, 0, 0, initial, finall); } // Print the number of operations document.write(ans); } // Function to count the number of // flips required to change initial // node values to final node value function countOperations(N, initial, finall, Edges) { // Add the given edges for (let i = 0; i < N - 1; i++) { addEdges(Edges[i][0], Edges[i][1]); } // DFS Traversal DFS(N + 1, initial, finall); } let Edges = [ [ 1, 2 ], [ 1, 3 ] ]; let initial = [ true , true , false ]; let finall = [ false , true , true ]; countOperations(N, initial, finall, Edges); // This code iscontributed by decode2207. </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)