Retrieve back the Array CodeChef Solution – Queslers

Problem : Retrieve back the Array CodeChef 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].

Retrieve back the Array CodeChef Solution in C++

#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, x;

void solve()
{
    cin>>n>>x;

    if(n==1){
        cout<<x;
        return;
    }

    int y = 0;
    int ans[n];
    for(int i = 0; i<n-1; i++){
        ans[i] = i;
        y ^= i;
    }

    int z = y^x;
    int temp = 1<<18;

    if(z>=n-1 && z<=500000){
        ans[n-1] = z;
    }
    else{
        ans[n-1] = z^temp;
        if((ans[n-2] ^ temp) == ans[n-1]){
            ans[0] ^= temp;
        }
        else{
            ans[n-2] ^= temp;
        }
    }
    for(int i = 0; i<n; i++){
        cout<<ans[i]<<' ';
    }
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}

Retrieve back the Array CodeChef Solution in Java

import java.io.*;
import java.util.*;

public class Main {
    //--------------------------INPUT READER---------------------------------//
    static class fs {
        public BufferedReader br;
        StringTokenizer st = new StringTokenizer("");

        public fs() { this(System.in); }
        public fs(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String next() {
            while (!st.hasMoreTokens()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }

        int ni() { return Integer.parseInt(next()); }
        long nl() { return Long.parseLong(next()); }
        double nd() { return Double.parseDouble(next()); }
        String ns() { return next(); }

        int[] na(long nn) {
            int n = (int) nn;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        long[] nal(long nn) {
            int n = (int) nn;
            long[] l = new long[n];
            for(int i = 0; i < n; i++) l[i] = nl();
            return l;
        }
    }
    //-----------------------------------------------------------------------//

    //---------------------------PRINTER-------------------------------------//
    static class Printer {
        static PrintWriter w;
        public Printer() {this(System.out);}
        public Printer(OutputStream os) {
            w = new PrintWriter(os, true);
        }
        public void p(int i) {w.println(i);}
        public void p(long l) {w.println(l);}
        public void p(double d) {w.println(d);}
        public void p(String s) { w.println(s);}
        public void pr(int i) {w.print(i);}
        public void pr(long l) {w.print(l);}
        public void pr(double d) {w.print(d);}
        public void pr(String s) { w.print(s);}
        public void pl() {w.println();}
        public void close() {w.close();}
    }
    //-----------------------------------------------------------------------//

    //--------------------------VARIABLES------------------------------------//
    static fs sc = new fs();
    static OutputStream outputStream = System.out;
    static Printer w = new Printer(outputStream);
    static long lma = Long.MAX_VALUE, lmi = Long.MIN_VALUE;
    static int ima = Integer.MAX_VALUE, imi = Integer.MIN_VALUE;
    static long mod = 1000000007;
    //-----------------------------------------------------------------------//

    //--------------------------ADMIN_MODE-----------------------------------//
    private static void ADMIN_MODE() throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            w = new Printer(new FileOutputStream("output.txt"));
            sc = new fs(new FileInputStream("input.txt"));
        }
    }
    //-----------------------------------------------------------------------//

    //----------------------------START--------------------------------------//
    public static void main(String[] args)
            throws IOException {

        //  ADMIN_MODE();

        int t = sc.ni();while(t-->0)
            solve();


        w.close();
    }

    static Random rnd = new Random();

    static int btw(int l, int r) {
        return Math.abs(rnd.nextInt())%(r-l+1)+l;
    }

    static void solve() throws IOException {
        int n = sc.ni();
        int xor = sc.ni();
        char[] strr = Integer.toString(xor, 2).toCharArray();
        int[] xrr = new int[32];
        int id = strr.length-1;
        for(int i = 0; i < strr.length; i++) {
            xrr[i] = (strr[id--]=='1'?1:0);
        }

        List<Integer> li = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            li.add(0);
        }

        for(int i = 0; (i < strr.length) || !diff(li); i++) {
            int curr = xrr[i];

            int one = 0, zer = 0;
            int add = (int)Math.pow(2, i);
            List<Integer> nn = new ArrayList<>();

            nn.add(li.get(0));
            zer++;
            int last = -1;
            int diff = -1;
            boolean on = true;
            for(int j = 1; j < n; j++) {
                if(li.get(j-1).equals(li.get(j))) {
                    if(on) {
                        nn.add(li.get(j) + add);
                        last = j;
                        one++;
                        on = false;
                    } else {
                        nn.add(li.get(j));
                        zer++;
                        on = true;
                    }
                } else {
                    if(diff == -1 && (j == n-1 || !li.get(j+1).equals(j))) {
                        diff = j;
                    }

                    on = true;
                    nn.add(li.get(j));
                    last = j;
                    zer++;
                }
            }

            if((curr == 1 && one%2==0) || (curr == 0 && one%2==1)) {
                if(diff != -1) {
                    nn.set(diff, nn.get(diff)+add);
                } else {
                    if (last != -1 && one >= zer) {
                        nn.set(last, nn.get(last) - add);
                    } else {
                        nn.set(0, nn.get(0) + add);
                    }
                }
            }

            li = nn;
            li.sort(Integer::compare);
        }

        for(int i = 0; i < n; i++) {
            w.pr(li.get(i)+" ");
        }
        w.pl();
    }

    static boolean diff(List<Integer> li) {
        for(int i = 1; i < li.size(); i++) {
            if(li.get(i).equals(li.get(i-1))) return false;
        }
        return true;
    }
}

Retrieve back the Array CodeChef Solution in Python

# cook your dish here
# def modifyBit( n,  p,  b):
#     mask = 1 << p
#     return (n & ~mask) | ((b << p) & mask)
    
    
for _ in range(int(input())):
    max1 = 500000
    n , x = map(int,input().split())
    if n == 1:
        print(x)
    elif n == 2:
        print(0,x)
    else:
        lst = []
        xor = 0 
        for i in range(n-1):
            xor = xor^i
            lst.append(i)
        # if (xor^x) < n-1:
        #     res = modifyBit(xor^x,18,1)
        #     last = modifyBit(lst[n-2],18,1)
        #     lst.pop()
        #     lst.append(last)
        #     print(*lst,sep=' ',end=" ")
        #     print(res)
        # elif (xor^x) > (5*(10**5)):
        #     res = modifyBit(xor^x,18,0)
        #     first = modifyBit(lst[0],18,1)
        #     lst.pop(0)
        #     lst.insert(0,first)
        #     print(*lst,sep=' ',end=" ")
        #     print(res)
            
        # else:
        #     print(*lst,sep=' ',end=" ")
        #     print(xor^x)
        last = x^xor
        set_18 = (1<<18)
        
        if last >= n-1 and last <= max1:
            # print(*lst,sep=' ',end=" ")
            lst.append(last)
        else:
            lst.append(last^set_18)
            if (lst[0]^set_18) == lst[n-1]:
                lst[1] ^= set_18
            else:
                lst[0] ^= set_18
        print(*lst,sep=" ",end=" ")
            # print(last)
            
        

Retrieve back the Array CodeChef Solution Review:

In our experience, we suggest you solve this Retrieve back the Array CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

Retrieve back the Array Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Retrieve back the Array CodeChef Solution.

Conclusion:

I hope this Retrieve back the Array CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More CodeChef Solutions >>

Olympics Ranking CodeChef Solution

Problem Difficulties CodeChef Solution

Chef and Bulb Invention CodeChef Solution

Array Filling CodeChef Solution

Special Triplets CodeChef Solution