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; } };
|