Given an N-ary Tree consisting of N nodes valued from 1 to N, an array arr[] consisting of N positive integers, where arr[i] is the value associated with the ith node, and Q queries, each consisting of a node. The task for each query is to find the Bitwise OR of node values present in the subtree of the given node.
Examples:
Input: arr[] = {2, 3, 4, 8, 16} Queries[]: {2, 3, 1}
Output: 3 28 31
Explanation:
Query 1: Bitwise OR(subtree(Node 2)) = Bitwise OR(Node 2) = Bitwise OR(3) = 3
Query 2: Bitwise OR(subtree(Node 3)) = Bitwise OR(Node 3, Node 4, Node 5) = Bitwise OR(4, 8, 16) = 28
Query 3: Bitwise OR(subtree(Node 1)) = Bitwise OR(Node1, Node 2, Node 3, Node 4, Node 5) = Bitwise OR(2, 3, 4, 8, 16) = 31Input: arr[] = {2, 3, 4, 8, 16} Queries[]: {4, 5}
Output: 8 16
Explanation:
Query 1: Bitwise OR(subtree(Node 4)) = bitwise OR(Node 4) = 8
Query 2: Bitwise OR(subtree(Node 5)) = bitwise OR(Node 5) = 16
Naive Approach: The simplest approach to solve this problem is to traverse the subtree of the given node and for each query, calculate the Bitwise OR of every node in the subtree of that node and print that value.
Time Complexity: O(Q * N)
Auxiliary Space: O(Q * N)
Efficient Approach: To optimize the above approach, the idea is to precompute the Bitwise OR of all subtrees present in the given tree, and for each query, find the Bitwise XOR of subtrees for every given node. Follow the steps below to solve the problem:
- Initialize a vector ans[] to store the Bitwise OR of all subtrees present in the given Tree.
- Precompute the Bitwise OR for every subtree using Depth First Search(DFS).
- If the node is a leaf node, the bitwise OR of this node is the node value itself.
- Otherwise, the Bitwise OR for the subtree is equal to the Bitwise OR of all subtree values of its children.
- After completing the above steps, print the value stored at ans[Queries[i]] for every ith query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Maximum Number of nodesconst int N = 1e5 + 5;// Adjacency listvector<int> adj[N];// Stores Bitwise OR of each nodevector<int> answer(N);// Function to add edges to the Treevoid addEdgesToGraph(int Edges[][2], int N){ // Traverse the edges for (int i = 0; i < N - 1; i++) { int u = Edges[i][0]; int v = Edges[i][1]; // Add edges adj[u].push_back(v); adj[v].push_back(u); }}// Function to perform DFS// Traversal on the given treevoid DFS(int node, int parent, int Val[]){ // Initialize answer with bitwise // OR of current node answer[node] = Val[node]; // Iterate over each child // of the current node for (int child : adj[node]) { // Skip parent node if (child == parent) continue; // Call DFS for each child DFS(child, node, Val); // Taking bitwise OR of the // answer of the child to // find node's OR value answer[node] = (answer[node] | answer[child]); }}// Function to call DFS from the'=// root for precomputing answersvoid preprocess(int Val[]){ DFS(1, -1, Val);}// Function to calculate and print// the Bitwise OR for Q queriesvoid findSubtreeOR(int Queries[], int Q, int Val[]){ // Perform preprocessing preprocess(Val); // Iterate over each given query for (int i = 0; i < Q; i++) { cout << answer[Queries[i]] << ' '; }}// Utility function to find and// print bitwise OR for Q queriesvoid findSubtreeORUtil( int N, int Edges[][2], int Val[], int Queries[], int Q){ // Function to add edges to graph addEdgesToGraph(Edges, N); // Function call findSubtreeOR(Queries, Q, Val);}// Driver Codeint main(){ // Number of nodes int N = 5; int Edges[][2] = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } }; int Val[] = { 0, 2, 3, 4, 8, 16 }; int Queries[] = { 2, 3, 1 }; int Q = sizeof(Queries) / sizeof(Queries[0]); // Function call findSubtreeORUtil(N, Edges, Val, Queries, Q); return 0;} |
Java
// Java program for above approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Maximum Number of nodes static int N = (int)1e5 + 5; // Adjacency list static ArrayList<ArrayList<Integer>> adj; // Stores Bitwise OR of each node static int[] answer; // Function to add edges to the Tree static void addEdgesToGraph(int Edges[][], int N) { // Traverse the edges for (int i = 0; i < N - 1; i++) { int u = Edges[i][0]; int v = Edges[i][1]; // Add edges adj.get(u).add(v); adj.get(v).add(u); } } // Function to perform DFS // Traversal on the given tree static void DFS(int node, int parent, int Val[]) { // Initialize answer with bitwise // OR of current node answer[node] = Val[node]; // Iterate over each child // of the current node for (Integer child : adj.get(node)) { // Skip parent node if (child == parent) continue; // Call DFS for each child DFS(child, node, Val); // Taking bitwise OR of the // answer of the child to // find node's OR value answer[node] = (answer[node] | answer[child]); } } // Function to call DFS from the'= // root for precomputing answers static void preprocess(int Val[]) { DFS(1, -1, Val); } // Function to calculate and print // the Bitwise OR for Q queries static void findSubtreeOR(int Queries[], int Q, int Val[]) { // Perform preprocessing preprocess(Val); // Iterate over each given query for (int i = 0; i < Q; i++) { System.out.println(answer[Queries[i]] + " "); } } // Utility function to find and // print bitwise OR for Q queries static void findSubtreeORUtil(int N, int Edges[][], int Val[], int Queries[], int Q) { // Function to add edges to graph addEdgesToGraph(Edges, N); // Function call findSubtreeOR(Queries, Q, Val); } // Driver function public static void main (String[] args) { adj = new ArrayList<>(); for(int i = 0; i < N; i++) adj.add(new ArrayList<>()); answer = new int[N]; N = 5; int Edges[][] = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } }; int Val[] = { 0, 2, 3, 4, 8, 16 }; int Queries[] = { 2, 3, 1 }; int Q = Queries.length; // Function call findSubtreeORUtil(N, Edges, Val, Queries, Q); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Maximum Number of nodesN = 100005; # Adjacency listadj = [[] for i in range(N)]; # Stores Bitwise OR of each nodeanswer = [0 for i in range(N)] # Function to add edges to the Treedef addEdgesToGraph(Edges, N): # Traverse the edges for i in range(N - 1): u = Edges[i][0]; v = Edges[i][1]; # Add edges adj[u].append(v); adj[v].append(u); # Function to perform DFS# Traversal on the given treedef DFS(node, parent, Val): # Initialize answer with bitwise # OR of current node answer[node] = Val[node]; # Iterate over each child # of the current node for child in adj[node]: # Skip parent node if (child == parent): continue; # Call DFS for each child DFS(child, node, Val); # Taking bitwise OR of the # answer of the child to # find node's OR value answer[node] = (answer[node] | answer[child]); # Function to call DFS from the'=# root for precomputing answersdef preprocess( Val): DFS(1, -1, Val);# Function to calculate and print# the Bitwise OR for Q queriesdef findSubtreeOR(Queries, Q, Val): # Perform preprocessing preprocess(Val); # Iterate over each given query for i in range(Q): print(answer[Queries[i]], end=' ') # Utility function to find and# print bitwise OR for Q queriesdef findSubtreeORUtil( N, Edges, Val, Queries, Q): # Function to add edges to graph addEdgesToGraph(Edges, N); # Function call findSubtreeOR(Queries, Q, Val); # Driver Codeif __name__=='__main__': # Number of nodes N = 5; Edges = [ [ 1, 2 ], [ 1, 3 ], [ 3, 4 ], [ 3, 5 ] ]; Val = [ 0, 2, 3, 4, 8, 16 ]; Queries = [ 2, 3, 1 ]; Q = len(Queries) # Function call findSubtreeORUtil(N, Edges, Val,Queries, Q); # This code is contributed by rutvik_56 |
C#
// C# program to generate// n-bit Gray codesusing System;using System.Collections.Generic;class GFG { // Maximum Number of nodes static int N = (int)1e5 + 5; // Adjacency list static List<List<int> > adj; // Stores Bitwise OR of each node static int[] answer; // Function to Add edges to the Tree static void AddEdgesToGraph(int[, ] Edges, int N) { // Traverse the edges for (int i = 0; i < N - 1; i++) { int u = Edges[i, 0]; int v = Edges[i, 1]; // Add edges adj[u].Add(v); adj[v].Add(u); } } // Function to perform DFS // Traversal on the given tree static void DFS(int node, int parent, int[] Val) { // Initialize answer with bitwise // OR of current node answer[node] = Val[node]; // Iterate over each child // of the current node foreach(int child in adj[node]) { // Skip parent node if (child == parent) continue; // Call DFS for each child DFS(child, node, Val); // Taking bitwise OR of the // answer of the child to // find node's OR value answer[node] = (answer[node] | answer[child]); } } // Function to call DFS from the'= // root for precomputing answers static void preprocess(int[] Val) { DFS(1, -1, Val); } // Function to calculate and print // the Bitwise OR for Q queries static void findSubtreeOR(int[] Queries, int Q, int[] Val) { // Perform preprocessing preprocess(Val); // Iterate over each given query for (int i = 0; i < Q; i++) { Console.Write(answer[Queries[i]] + " "); } } // Utility function to find and // print bitwise OR for Q queries static void findSubtreeORUtil(int N, int[, ] Edges, int[] Val, int[] Queries, int Q) { // Function to Add edges to graph AddEdgesToGraph(Edges, N); // Function call findSubtreeOR(Queries, Q, Val); } // Driver function public static void Main(String[] args) { adj = new List<List<int> >(); for (int i = 0; i < N; i++) adj.Add(new List<int>()); answer = new int[N]; N = 5; int[, ] Edges = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } }; int[] Val = { 0, 2, 3, 4, 8, 16 }; int[] Queries = { 2, 3, 1 }; int Q = Queries.Length; // Function call findSubtreeORUtil(N, Edges, Val, Queries, Q); }}// This code is contributed by grand_master. |
Javascript
<script>// Javascript program for the above approach// Maximum Number of nodesconst N = 1e5 + 5;// Adjacency listlet adj = [];for (let i = 0; i < N; i++) { adj.push([])}// Stores Bitwise OR of each nodelet answer = new Array(N);// Function to add edges to the Treefunction addEdgesToGraph(Edges, N) { // Traverse the edges for (let i = 0; i < N - 1; i++) { let u = Edges[i][0]; let v = Edges[i][1]; // Add edges adj[u].push(v); adj[v].push(u); }}// Function to perform DFS// Traversal on the given treefunction DFS(node, parent, Val) { // Initialize answer with bitwise // OR of current node answer[node] = Val[node]; // Iterate over each child // of the current node for (let child of adj[node]) { // Skip parent node if (child == parent) continue; // Call DFS for each child DFS(child, node, Val); // Taking bitwise OR of the // answer of the child to // find node's OR value answer[node] = (answer[node] | answer[child]); }}// Function to call DFS from the'=// root for precomputing answersfunction preprocess(Val) { DFS(1, -1, Val);}// Function to calculate and print// the Bitwise OR for Q queriesfunction findSubtreeOR(Queries, Q, Val) { // Perform preprocessing preprocess(Val); // Iterate over each given query for (let i = 0; i < Q; i++) { document.write(answer[Queries[i]] + ' '); }}// Utility function to find and// print bitwise OR for Q queriesfunction findSubtreeORUtil(N, Edges, Val, Queries, Q) { // Function to add edges to graph addEdgesToGraph(Edges, N); // Function call findSubtreeOR(Queries, Q, Val);}// Driver Code// Number of nodeslet n = 5;let Edges = [[1, 2], [1, 3], [3, 4], [3, 5]];let Val = [0, 2, 3, 4, 8, 16];let Queries = [2, 3, 1];let Q = Queries.length;// Function callfindSubtreeORUtil(n, Edges, Val, Queries, Q);// This code is contributed by _saurabh_jaiswal</script> |
Output:
3 28 31
Time Complexity: O(N + Q)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
