Retrieve back the Array XORED Solution Codechef

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 1

Sample Output 1

10
7 3
5 6 2

Explanation

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

January Long Challenge 2022 Solution

Leave a Comment

four × 2 =