Given a list S that initially contains a single value 0. Below are the Q queries of the following types:
- 0 X: Insert X in the list
- 1 X: For every element A in S, replace it by A XOR X.
The task is to print all the element in the list in increasing order after performing the given Q queries.
Examples:
Input: Q[][] = { {0, 6}, {0, 3}, {0, 2}, {1, 4}, {1, 5} }
Output: 1 2 3 7
Explanation:
[0] (initial value)
[0 6] (add 6 to list)
[0 6 3] (add 3 to list)
[0 6 3 2] (add 2 to list)
[4 2 7 6] (XOR each element by 4)
[1 7 2 3] (XOR each element by 5)
Thus sorted order after performing queries is [1 2 3 7]Input: Q[][]= {{0, 2}, {1, 3}, {0, 5} }
Output: 1 3 5
Explanation:
[0] (initial value)
[0 2] (add 2 to list)
[3 1] (XOR each element by 3)
[3 1 5] (add 5 to list)
Thus sorted order after performing queries is [1 3 5]
Naive Approach: The simplest approach to solve the problem is:
- Initialize a list with 0 then traverse for each query and do the following:
- For query type 0 add given value in the list.
- For query type 1 traverse list and update every element with their respective Bitwise XOR with value.
- After all the queries performed, print the final list in increasing order.
Time Complexity: O(N*Q+Q*log(Q)), where N is the length of the list and Q is the number of queries
Auxiliary Space: O(1)
Efficient Approach: It is much easier to process the numbers in reverse order by keeping track of the cumulative Bitwise XOR working from right to left. Follow the steps below to solve the problem:
- Initialize a variable xor with 0.
- Iterate over the query array from right to left, add xor^value to the list while query type is 0 otherwise update xor with xor^value.
- After traversing query add xor to the list and sort the final list.
- Print the final list after the above operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 5#define M 2// Function to return required list// after performing all the querieslist<int> ConstructList(int Q[N][M]){ // Store cumulative Bitwise XOR int xr = 0; // Initialize final list to return list<int> ans; // Perform each query for (int i = N - 1; i >= 0; i--) { if (Q[i][0] == 0) ans.push_back(Q[i][1] ^ xr); else xr ^= Q[i][1]; } // The initial value of 0 ans.push_back(xr); // Sort the list ans.sort(); // Return final list return ans;}// Driver Codeint main(){ // Given Queries int Q[N][M] = {{ 0, 6 }, { 0, 3 }, { 0, 2 }, { 1, 4 }, { 1, 5 }}; // Function Call list<int> ans = ConstructList(Q); for (auto it = ans.begin(); it != ans.end(); ++it) cout << ' ' << *it;}// This code is contributed by gauravrajput1 |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to return required list // after performing all the queries static List<Integer> ConstructList(int[][] Q) { // Store cumulative Bitwise XOR int xor = 0; // Initialize final list to return List<Integer> ans = new ArrayList<>(); // Perform each query for (int i = Q.length - 1; i >= 0; i--) { if (Q[i][0] == 0) ans.add(Q[i][1] ^ xor); else xor ^= Q[i][1]; } // The initial value of 0 ans.add(xor); // Sort the list Collections.sort(ans); // Return final list return ans; } // Driver Code public static void main(String[] args) { // Given Queries int[][] Q = { { 0, 6 }, { 0, 3 }, { 0, 2 }, { 1, 4 }, { 1, 5 } }; // Function Call System.out.println(ConstructList(Q)); }} |
Python3
# Python3 program for the above approach # Function to return required list# after performing all the queriesdef ConstructList(Q): # Store cumulative Bitwise XOR xor = 0 # Initialize final list to return ans = [] # Perform each query for i in range(len(Q) - 1, -1, -1): if(Q[i][0] == 0): ans.append(Q[i][1] ^ xor) else: xor ^= Q[i][1] # The initial value of 0 ans.append(xor) # Sort the list ans.sort() # Return final list return ans# Driver Code# Given QueriesQ = [ [0, 6], [0, 3], [0, 2], [1, 4], [1, 5] ]# Function callprint(ConstructList(Q))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to return required list // after performing all the queries static List<int> ConstructList(int[,] Q) { // Store cumulative Bitwise XOR int xor = 0; // Initialize readonly list to return List<int> ans = new List<int>(); // Perform each query for (int i = Q.GetLength(0) - 1; i >= 0; i--) { if (Q[i, 0] == 0) ans.Add(Q[i, 1] ^ xor); else xor ^= Q[i, 1]; } // The initial value of 0 ans.Add(xor); // Sort the list ans.Sort(); // Return readonly list return ans; } // Driver Code public static void Main(String[] args) { // Given Queries int[,] Q = {{ 0, 6 }, { 0, 3 }, { 0, 2 }, { 1, 4 }, { 1, 5 }}; // Function Call foreach( int i in ConstructList(Q)) Console.Write(i + ", "); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approachvar N = 5var M = 2// Function to return required list// after performing all the queriesfunction ConstructList(Q){ // Store cumulative Bitwise XOR var xr = 0; // Initialize final list to return var ans = []; // Perform each query for (var i = N - 1; i >= 0; i--) { if (Q[i][0] == 0) ans.push(Q[i][1] ^ xr); else xr ^= Q[i][1]; } // The initial value of 0 ans.push(xr); // Sort the list ans.sort((a,b)=>a-b); // Return final list return ans;}// Driver Code// Given Queriesvar Q = [[ 0, 6 ], [ 0, 3 ], [ 0, 2 ], [ 1, 4 ], [ 1, 5 ]];// Function Callvar ans = ConstructList(Q);ans.forEach(element => { document.write(" "+element);});// This code is contributed by famously.</script> |
[1, 2, 3, 7]
Time Complexity: O(Q * log(Q)), where Q is the number of queries.
Auxiliary Space: O(N), where N is the number of elements in the resultant list.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
