[Geeks for Geeks] Construct list using given q XOR queries

Construct list using given q XOR queries

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.

Print all the element in the list in increasing order after performing the given Q queries.

  • Time : O(nlogn)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
vector<int> constructList(vector<vector<int>> Q, int N) {
vector<int> res{0};
queue<pair<int, int>> op;
int XOR = 0;

for(auto& q : Q) {
if(q[0] == 0) res.push_back(q[1]);
else {
op.push({res.size(), q[1]});
XOR ^= q[1];
}
}

for(int i = 0; i < res.size(); i++) {
while(!op.empty() and op.front().first == i) {
XOR ^= op.front().second;
op.pop();
}
res[i] ^= XOR;
}

sort(begin(res), end(res));

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/27/PS/GeeksforGeeks/construct-list-using-given-q-xor-queries/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.