Retrieve back the Array XORED Solution Codechef

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

Subtasks

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

Sample Input 1 

3
1 10
2 4
3 1

Sample Output 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].

January Long Challenge 2022
January Long Challenge 2022

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

January Long Challenge 2022 Solution

December Long Challenge 2021 Solution

Leave a Comment

twelve − 6 =