Non Zero Subarray Xor Solution|Codesheff starter 23 rated for div 3

JJ is back with another challenge. He challenges you to construct an array A$A$ containing N$N$ integers such that the following conditions hold:

• For all 1≤i≤N$1\le i\le N$, 1≤Ai≤106$1\le A_i\le {10}^6$
• Every subarray has non-zero XOR. That is, for every 1≤L≤R≤N$1\le L\le R\le N$, AL⊕AL+1⊕…⊕AR≠0$A_L\oplus A_{L+1}\oplus \dots \oplus A_R\ne 0$. Here, ⊕$\oplus$ denotes the bitwise XOR operation.

Can you complete JJ's challenge?

Under the given constraints, it can be proved that there always exists at least one array satisfying these conditions. If there are multiple possible arrays, print any of them.

Input Format

• The first line contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains an integer N$N$ — the size of the array A$A$ to be constructed.

Output Format

For each test case, output a single line containing N$N$ space-separated integers, denoting the elements of array A$A$. The ith$i^{th}$ of these N$N$ integers is Ai$A_i$. If multiple arrays exist which satisfy the conditions, print any of them.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤105$1\le N\le {10}^5$
• It is guaranteed that the sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

3
1
6
6

Sample Output 1 

7
1 2 4 8 16 32
2 3 5 7 11 13

Explanation

Test Case 1$1$: There is only one subarray, [7]$[7]$. Its XOR is non-zero.

Test Case 2$2$: Some of the subarray XORS are:

• XOR([2,4,8])=14≠0$\mathtt{\text{XOR}}([2,4,8])=14\ne 0$
• XOR([1,2])=3≠0$\mathtt{\text{XOR}}([1,2])=3\ne 0$
• XOR([4,8,16,32])=60≠0$\mathtt{\text{XOR}}([4,8,16,32])=60\ne 0$.

Similarly, it can be checked that every subarray has non-zero XOR.

Test Case 3$3$: Some of the subarray XORS are:

• XOR([2,3,5,7])=3≠0$\mathtt{\text{XOR}}([2,3,5,7])=3\ne 0$
• XOR([7,11])=12≠0$\mathtt{\text{XOR}}([7,11])=12\ne 0$
• XOR([2,3,5,7,11,13])=5≠0$\mathtt{\text{XOR}}([2,3,5,7,11,13])=5\ne 0$

Similarly, it can be checked that every subarray has non-zero XOR.

Solution:

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(false), cin.tie(NULL);

#define int long long

#define rep(i, n) for (int i = 0; i < n; i++)

#define repi(i, x, n) for (int i = x; i < n; i++)

#define br cout << endl

#define vi vector<int>

using namespace std;

int fun(int prev, int ptr) {

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

    if ((ptr & (1 << i)) > 0)

      prev ^= (1 << i);

  }

  return prev;

}

void solve() {

  int n;

  cin >> n;

  vector<int> res;

  map<int, int> s;

  s[0] = 1;

  int ptr = 1;

  int prev = 0;

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

    // cout<<ptr<<endl;

    while (s[fun(prev, ptr)] == 1) {

      ptr++;

    }

    prev = fun(prev, ptr);

    s[prev] = 1;

    res.push_back(ptr);

    ptr++;

  }

  for (auto x : res)

    cout << x << " ";

  cout << endl;

}

signed main() {

#ifndef ONLINE_JUDGE

  freopen("input.txt", "r", stdin);

  freopen("output.txt", "w", stdout);

#endif

  fastio int t;

  t = 1;

  cin >> t;

  while (t--) {

    solve();

  }

}