Retrieve back the Array XORED Solution Codechef

Page Contents

Codechef Retrieve back the Array XORED Solution

Dazzler had an array of NN distinct non-negative integers. Somehow he lost the array, but he knows the bitwise XOR of all the elements in the array. You have to help him to retrieve the array.

You are given two positive integers NN and XX. Construct an array AA of NN elements with the following conditions:

• For each ii (1≤i≤N1≤i≤N), 0≤Ai≤5⋅1050≤Ai≤5⋅105.
• All the elements in the array AA should be pairwise distinct, i.e, Ai≠AjAi≠Aj if i≠ji≠j
• The bitwise XOR of all the NN elements in the array should be equal to XX, i.e, A1⊕A2⊕…⊕AN=XA1⊕A2⊕…⊕AN=X, where ⊕⊕ denotes the bitwise XOR operation.

If there are multiple possible solutions, you may print any of them.

Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and XX — the size of the array and the bitwise XOR of the entire array.

Output Format

For each test case, output the NN distinct non-negative integers satisfying the constraints above.

Constraints

• 1≤T≤2⋅1051≤T≤2⋅105
• 1≤N≤1051≤N≤105
• 1≤X≤5⋅1051≤X≤5⋅105
• 0≤Ai≤5⋅1050≤Ai≤5⋅105
• The sum of NN over all test cases does not exceed 3⋅1053⋅105

• Subtask 1 (30 points): 1≤X≤1051≤X≤105
• Subtask 2 (70 points): 1≤X≤5⋅1051≤X≤5⋅105

```3
1 10
2 4
3 1```

```10
7 3
5 6 2```

Explanation

Test case 22: [7,3][7,3] is one possible array, because 7⊕3=47⊕3=4

Test case 33: [5,6,2][5,6,2] is one possible array, because 5⊕6⊕2=15⊕6⊕2=1. Another valid array is [8,20,29][8,20,29].

Solution

Program: Retrieve back the Array XORED Solution in C++

```#include<bits/stdc++.h>
using namespace std;
int main(){
long long t;
cin>>t;
while(t--){
long long n,k;
cin>>n>>k;
vector<long long>l;
unordered_map<long long, long long>a;
int q,j;
q=0;
j=0;
long long w=500001;
if (n==1){
l.push_back(k);
j=n;
}
while(j<n-1){
long long s=rand()%w;
if(a[s]==0){
q^=s;
l.push_back(s);
a[s]+=1;
j+=1;
}
else if (a[s]>0){
continue;
}

if (j==n-1){
long long o=k^q;
if (a[o]==0 && 0<=o && o<=500000){
q^=o;
l.push_back(o);
a[o]+=1;
j+=1;
}
else{
j-=1;
q^=l[0];
a[l[0]]-=1;
if (l.size()>0){
l.erase(l.begin());
}
}
}
}
for(auto i:l){
cout<<i<<" ";
}
cout<<"\n";
}
}```

Program: Retrieve back the Array XORED Solution in Java

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in=new Scanner(System.in);
long test=in.nextLong();
for(int x=1;x<=test;x++)
{
int N=in.nextInt();
int X=in.nextInt();
int K=(int)(Math.log(X)/Math.log(2)); K=K+1;
int counter=1;
int ans=0;int t=1;
if((K==19)&&((X&(1<<(K-2)))>0))
{
t=2;
}
if(N==1)
{
System.out.print(X);
}
if(N>1)
{
while(N>t)
{
if((counter&(1<<(K-1)))>0)
{
counter++;
continue;
}
System.out.print(counter+"  ");
ans=ans^counter;
counter++;
N--;
}
if(t==2)
{
counter=1<<(K-2);
System.out.print(counter+" ");
ans=ans^counter;
}
System.out.print(ans^X);
}
System.out.println();
}
}
}```

Program: Retrieve back the Array XORED Solution in Python

```import random
t = int(input())
while t>0:
t-=1
n, x = [int(ele) for ele in input().split(' ')]
if n==1:
print(x)
continue
while True:
numbers = random.sample(range(1, 5*(10**5)), n-1)
res = numbers[0]
for i in range(1,n-1):
res=res^numbers[i]

final = res ^ x
if final in numbers:
continue
if res^final!=x:
continue
if final>5*(10**5):
continue
for num in numbers:
print(num, end=' ')
print(final)
break```