XOR Query
You are given a tree(root 0) with N vertex having N - 1 edges. You are also given an array ‘QUERY’ of size ‘Q’, where each query consists of an integer that denotes a node. You have to print the xor of all the values of nodes in the sub-tree of the given node.

Note:

Here XOR denotes the bitwise operator (^).

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains two space-separated integers, ‘N’ and 'Q', denoting the number of nodes and the total queries operation to be performed. The next ‘N’-1 lines of each test case contain two integers representing an edge between the given indices. The next line of each test case contains ‘Q’ space-separated integers denoting the nodes of the tree on which query has to be performed.

Output Format:

For each test case, print ‘Q’ space-separated integers denoting the result of the queries. Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

XOR Query

You are given a tree(root 0) with N vertex having N - 1 edges. You are also given an array ‘QUERY’ of size ‘Q’, where each query consists of an integer that denotes a node. You have to print the xor of all the values of nodes in the sub-tree of the given node.

Note:

Here XOR denotes the bitwise operator (^).

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and 'Q', denoting the number of nodes and the total queries operation to be performed.

The next ‘N’-1 lines of each test case contain two integers representing an edge between the given indices.

The next line of each test case contains ‘Q’ space-separated integers denoting the nodes of the tree on which query has to be performed.

Output Format:

For each test case, print ‘Q’ space-separated integers denoting the result of the queries.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
0 <= N, Q <= 10^5 
0 <= QUERY[i] < N

Time Limit: 1 sec

Accepted Answer

This question is about finding the XOR of all values of nodes in the sub-tree of a given node in a tree.

Read the input values for the number of test cases, number of nodes, and number of queries.
Construct the tree using the given edges.
For each query, traverse the sub-tree of the given node and calculate the XOR of all node values.
Print the XOR values for each query.

Accepted Answer

Brute Force

The basic idea is to traverse the subtree for each given node in the query. We traverse the nodes using the DFS and compute the XOR value of the subtree while traversing the tree.

Here is the algorithm :

Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
Create an array (say, ‘RES’) to store the result of queries.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to traverse the queries.
- Call the DFS function to compute the XOR of the subtree and store the value returned by the function in the ‘RES’.
Return ‘RES’.

DFS(‘GRAPH’, ‘CURR’, ‘PREV’) (where ‘CURR’ is the current vertex and ‘PREV’ is the previous vertex traversed).

Create a variable (say, ‘VAL’) to store the XOR value and initialize it with ‘CURR’.
Traverse the adjacent vertices of the ‘CURR’ vertex (say, ‘V’)
- Check if ‘V’ is not equal to ‘PREV’
  - Recursively call the DFS function to traverse the tree and update the ‘VAL’ by taking the XOR of it by the value returned by the function.
Return ‘VAL’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of vertices.

For each vertex, we store its adjacent vertices; therefore, storing them in the form of a graph will require O(N) space. The recursive stack of the HELPER function will contain all the neighbors of a vertex, which at most can be ‘N’ vertices. Therefore, the overall space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * Q), where ‘N’ is the number of vertices and ‘Q’ is the number of queries.

We run a loop to answer all the queries which take O(Q) time and in the worst case for each query we traverse all the nodes which take O(N) time. Therefore, the overall time complexity will be O(N * Q).

C++ (g++ 5.4)

/*

    Time complexity: O(N * Q)

    Space complexity: O(N)

    

    Where 'N' is the number of vertices and 'Q' is the number of queries.

*/



// dfs function.

int dfs(vector> &graph, int curr, int prev) {

    

    // To store XOR value.

    int val = curr;

    

    for(int i = 0; i < graph[curr].size(); ++i) {

        

        // Check condition.

        if(graph[curr][i] != prev) {

            

            // Call dfs recursively and update value.

            val ^= dfs(graph, graph[curr][i], curr);

        }

    }

    

    return val;

}



vector XORquery(int n, vector> &edges, int q, vector &query) {

    

    // Create graph.

    vector> graph(n);

    for(int i = 0; i < n - 1; ++i) {

        graph[edges[i][0]].push_back(edges[i][1]);

    }

    

    // To store the result.

    vector res;

    

    // Run all the queries.

    for(int i = 0; i < q; ++i) {

        

        // Call function.

        res.push_back(dfs(graph, query[i], -1));

    }

    

    return res;

}

Java (SE 1.8)


/*
	Time complexity: O(N * Q)
	Space complexity: O(N)
	
	Where 'N' is the number of vertices and 'Q' is the number of queries.
*/

import java.util.ArrayList;

public class Solution {
	

	private static int dfs(ArrayList> graph, int curr, int prev) {
	 
		   // To store XOR value.
	    int val = curr;
	    
	    for(int i = 0; i < graph.get(curr).size(); ++i) {
	        
	        // Check condition.
			if (graph.get(curr).get(i) != prev) {
	            
	            // Call dfs recursively and update value.
				val ^= dfs(graph, graph.get(curr).get(i), curr);
	        }
	    }
	    
	    return val;
	}

	public static int[] XORquery(int n, int[][] edges, int q, int[] query) {

		// Create graph.
		ArrayList> graph = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; ++i) {

			graph.get(edges[i][0]).add(edges[i][1]);
		}

		// To store the result.
		int res[] = new int[q];

		// Run all the queries.
		for (int i = 0; i < q; ++i) {

			// Call function.
			res[i] = (dfs(graph, query[i], -1));
		}

		return res;

	}

}

Python (3.5)

'''
    Time complexity: O(N * Q)
    Space complexity: O(N)
    
    Where 'N' is the number of vertices and 'Q' is the number of queries.
'''

from typing import List

# dfs function.
def dfs(graph: List[List[int]], curr: int, prev: int) -> int:
    
    # To store XOR value.
    val = curr
    
    for i in range(len(graph[curr])):
        
        # Check condition.
        if graph[curr][i] != prev:
            
            # Call dfs recursively and update value.
            val ^= dfs(graph, graph[curr][i], curr)
    
    return val


def XORquery(n: int, edges: List[List[int]], q: int, query: List[int]) -> List[int]:
    
    # Create graph.
    graph = [[] for i in range(n)]
    for i in range(n - 1):
        graph[edges[i][0]].append(edges[i][1])
    
    # To store the result.
    res = []
    
    # Run all the queries.
    for i in range(q):
        
        # Call function.
        res.append(dfs(graph, query[i], -1))
    
    return res

Accepted Answer

Optimised Approach

The basic idea is to precompute the XOR of all the nodes of the sub-tree by traversing the tree. We start by storing the XOR values from the child node and then using the value of the child node for calculating the XOR values of all the nodes of the sub-tree of the parent node. We store these values in an array (say, ‘DP’) and then answer the queries in constant time.

Here is the algorithm :

Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
Create an array (say, ‘DP’) to store the pre-computed XOR values.
Call the function DFS to compute the values.
Create an array (say, ‘RES’) to store the result of queries.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to traverse the queries.
- Push ‘DP[QUERY[i]]’ in the ‘RES’.
Return ‘RES’.

DFS(‘GRAPH’, ‘CURR’, ‘PREV’, ‘DP’) (where ‘CURR’ is the current vertex and ‘PREV’ is the previous vertex traversed).

Create a variable (say, ‘VAL’) to store the XOR value and initialize it with ‘CURR’.
Traverse the adjacent vertices of the ‘CURR’ vertex (say, ‘V’)
- Check if ‘V’ is not equal to ‘PREV’
  - Recursively call the DFS function to traverse the tree and update the ‘VAL’ by taking the XOR of it by the value returned by the function.
Update ‘DP[CURR]’ with ‘VAL’.
Return ‘VAL’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of vertices.

For each vertex, we store its adjacent vertices; therefore, storing them in the form of a graph will require O(N) space. The recursive stack of the DFS function will contain all the neighbors of a vertex, which at most can be ‘N’ vertices. We also use the ‘DP’ array of size ‘N’ to store the pre-computed XOR values. Therefore, the overall space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N + Q), where ‘N’ is the number of vertices and ‘Q’ is the number of queries.

We traverse all the nodes once which takes O(N) time. We also run a loop to answer all the queries which take O(Q) time. Therefore, the overall time complexity will be O(N + Q).

C++ (g++ 5.4)

/*

    Time complexity: O(N + Q)

    Space complexity: O(N)

    

    Where 'N' is the number of vertices and 'Q' is the number of queries.

*/



// dfs function.

int dfs(vector> &graph, int curr, int prev, vector &dp) {

    

    // To store XOR value.

    int val = curr;

    

    for(int i = 0; i < graph[curr].size(); ++i) {

        

        // Check condition.

        if(graph[curr][i] != prev) {

            

            // Call dfs recursively and update value.

            val ^= dfs(graph, graph[curr][i], curr, dp);

        }

    }

    

    dp[curr] = val;

    

    return val;

}



vector XORquery(int n, vector> &edges, int q, vector &query) {

    

    // Create graph.

    vector> graph(n);

    for(int i = 0; i < n - 1; ++i) {

        graph[edges[i][0]].push_back(edges[i][1]);

    }

    

    // To store pre-computed XOR values.

    vector dp(n);

    

    // Call the function.

    dfs(graph, 0, -1, dp);

    

    // To store the result.

    vector res;

    

    // Run all the queries.

    for(int i = 0; i < q; ++i) {

        

        // Store the result.

        res.push_back(dp[query[i]]);

    }

    

    return res;

}

Java (SE 1.8)


/*
	Time complexity: O(N + Q)
	Space complexity: O(N)
	
	Where 'N' is the number of vertices and 'Q' is the number of queries.
*/
import java.util.ArrayList;

public class Solution {

	private static int dfs(ArrayList> graph, int curr, int prev, int[] dp) {

		// To store XOR value.
		int val = curr;

		for (int i = 0; i < graph.get(curr).size(); ++i) {

			// Check condition.
			if (graph.get(curr).get(i) != prev) {

				// Call dfs recursively and update value.
				val ^= dfs(graph, graph.get(curr).get(i), curr, dp);
			}
		}

		dp[curr] = val;

		return val;
	}

	public static int[] XORquery(int n, int[][] edges, int q, int[] query) {

		// Create graph.
		ArrayList> graph = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; ++i) {

			graph.get(edges[i][0]).add(edges[i][1]);
		}

		// To store pre-computed XOR values.
		int dp[] = new int[n];

		// Call the function.
		dfs(graph, 0, -1, dp);

		// To store the result.
		int res[] = new int[q];
		
		// Run all the queries.
		for (int i = 0; i < q; ++i) {

			// Store the result.
			res[i] = (dp[query[i]]);
		}

		return res;
	}

}

Python (3.5)

'''
    Time complexity: O(N + Q)
    Space complexity: O(N)
    
    Where 'N' is the number of vertices and 'Q' is the number of queries.
'''

from typing import List

# dfs function.
def dfs(graph: List[List[int]], curr: int, prev: int, dp: List[int]) -> int:
    
    # To store XOR value.
    val = curr
    
    for i in range(len(graph[curr])):
        
        # Check condition.
        if graph[curr][i] != prev:
            
            # Call dfs recursively and update value.
            val ^= dfs(graph, graph[curr][i], curr, dp)
    
    dp[curr] = val

    return val


def XORquery(n: int, edges: List[List[int]], q: int, query: List[int]) -> List[int]:
    
    # Create graph.
    graph = [[] for i in range(n)]
    for i in range(n - 1):
        graph[edges[i][0]].append(edges[i][1])
    
    # To store pre-computed XOR values.
    dp = [0 for _ in range(n)]
    
    # Call the function.
    dfs(graph, 0, -1, dp)

    # To store the result.
    res = []
    
    # Run all the queries.
    for i in range(q):
        
        # Call function.
        res.append(dp[query[i]])
    
    return res

You are given a tree(root 0) with N vertex having N - 1 edges. You are also given an array ‘QUERY’ of size ‘Q’, where each query consists of an integer that denotes a node. You have to print the xor of all the values of nodes in the sub-tree of the given node.

Note:

Input Format:

Output Format:

Note :

Constraints :

Top Protium Finance Software Developer interview questions & answers

Popular interview questions of Software Developer