Contents
Codechef Retrieve back the Array XORED Solution
Dazzler had an array of N 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 N and X. Construct an array A of N elements with the following conditions:
- For each ii (1≤i≤N), 0≤Ai≤5⋅105.
- All the elements in the array A should be pairwise distinct, i.e, Ai≠Aj if i≠j
- The bitwise XOR of all the N elements in the array should be equal to X, i.e, A1⊕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 T, denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two space-separated integers N and X the size of the array and the bitwise XOR of the entire array.
Output Format
For each test case, output the N distinct non-negative integers satisfying the constraints above.
Constraints
- 1≤T≤2⋅105
- 1≤N≤105
- 1≤X≤5⋅105
- 0≤Ai≤5⋅105
- The sum of N over all test cases does not exceed 3⋅105
Subtasks
- Subtask 1 (30 points): 1≤X≤105
- Subtask 2 (70 points): 1≤X≤5⋅105
Sample Input 1
3
1 10
2 4
3 1Sample Output 1
10
7 3
5 6 2Explanation
Test case 2: [7,3] is one possible array, because 7⊕3=4
Test case 3: [5,6,2] is one possible array, because 5⊕6⊕2=1. Another valid array is [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