# XORED - Editorial

Setter: Sandeep V
Tester: Manan Grover
Editorialist: Kanhaiya Mohan

Easy

Bitwise Xor

# PROBLEM:

Given two positive integers N and X, construct an array A of N elements such that:

• For each i (1 \leq i \leq N), 0 \leq A_i \leq 5 \cdot 10^5.
• All the elements in the array A are pairwise distinct.
• Bitwise Xor of all the N elements of the array is X.

# QUICK EXPLANATION:

• For N = 1, the first and only element of the array is X.
• For N>1, Set the array as A_i = i (0 \leq i < N). Let Y be the bitwise xor of the first N-1 values. Then, the last element of the array will be Z = YβX.
• If Z lies outside the given range or matches with one of the first N-1 elements, toggle its 19^{th} bit.
• To maintain the bitwise xor of the whole array as X, toggle the 19^{th} bit of one other element.

# EXPLANATION:

Easier Version - One duplicate possible

For an easier version, let us think of constructing an array having atmost 1 duplicate and satisfying all other conditions.

Solution

Let A_i = i for 0 \leq i < N-1, and Y denote the bitwise xor of the first N-1 values of this array. We can set the last element of the array as YβX. This way,

• The bitwise xor of all the elements of the array = Y (bitwise xor of first N-1 elements) β (YβX) (last element) = (YβY)βX = X.
• Since the first N-1 elements are pairwise distinct, regardless of the value of the last element, there can only be 1 duplicate at maximum.

Based the idea of the easier version, let us set A_i = i for 0 \leq i < N-1. Let Y denote the bitwise xor of the first N-1 values of this array. To make the bitwise xor of the whole array X, the last element should be Z = YβX.

We can categorise the possible values of Z as:

• Category 1: (N-1 \leq Z \leq 5 \cdot 10^5) - Since the value of Z is within the bounds, it is a possible candidate. Also, Z is greater than all other elements in the array, therefore, ensuring that all the elements are pairwise distinct. We can simply set the last element as Z.
• Category 2: (Z < N-1) - The maximum value of N is 10^5. This means that all bits beyond the 18^{th} bit of Z must be unset. We can set the 19^{th} bit of Z to transform Z into the first category and place it as the last element.
• Category 3: (Z > 5 \cdot 10^5) - Let us look at the maximum value Z can take. We know that Z = YβX. This implies that the maximum number of set bits in Z would be less than or equal to that of X and Y. Since the maximum out of these is X and X \leq 5 \cdot 10^5 which takes 19 bits at maximum, we can say that Z<2^{19}.
Thus, the updated range of Z is (5 \cdot 10^5 \leq Z < 2^{19}). This means that the 19^{th} bit of Z is set. Turning off the 19^{th} bit of Z would transform it into one of the first two categories. We can then place it as the last element.

Note that while transforming Z (category two and three), we toggle the 19^{th} bit of Z. Thus, the bitwise xor of the array becomes (Xβ2^{18}). To revert this effect, we can set the 19^{th} bit of one other element. Based on the value of current Z, we have to make sure that all the elements are pairwise distinct.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
def firstXOR(n):
if n % 4 == 0 :
return n
if n % 4 == 1 :
return 1
if n % 4 == 2 :
return n + 1
return 0
t=int(input())
from random import *
for _ in range(t):

n,x=map(int,input().split())
if(n==1):
print(x)
continue
ans=[]
if(x<=10**5):
c=firstXOR(n-2)
if(firstXOR(n-2)==x):
for i in range(0,n-2):
ans.append(i)
c=firstXOR(n-3)
ans.append(2*(10**5))
ans.append(c^(2*(10**5))^x)
else:
for i in range(1,n-1):
ans.append(i)
ans.append(2*(10**5))
ans.append(c^(2*(10**5))^x)
else:
c=firstXOR(n-1)
if(c==0):
for i in range(1,n):
ans.append(i)
ans.append(x)
elif(c==1):
ans.append(0)
for i in range(2,n):
ans.append(i)
ans.append(x)
elif(c==n-1):
for i in range(0,n-1):
ans.append(i)
ans.append(x)
else:
ans.append(0)
if(x==(5*10**5)):
for i in range(2,n-1):
ans.append(i)
ans.append(368928)
ans.append(368928^x)
else:
for i in range(1,n-1):
ans.append(i)
ans.append(1^x)
print(*ans)

Tester's Editorial
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
int temp = 1 << 18;
int ns = 0;
while(t--){
int n, x;
n = readInt(1, 100000, ' ');
ns += n;
assert(ns <= 300000);
if(n == 1){
cout<<x<<"\n";
continue;
}
int ans[n];
for(int i = 0; i < n - 1; i++){
x ^= i;
ans[i] = i;
}
if(x >= n && x <= 500000){
ans[n - 1] = x;
}else{
if(x > 500000){
ans[n - 1] = x - temp;
}else{
ans[n - 1] = x + temp;
}
if(ans[n - 1] == n - 2 + temp){
ans[0] = temp;
}else{
ans[n - 2] += temp;
}
}
for(int i = 0; i < n; i++){
cout<<ans[i]<<" ";
}
cout<<"\n";
}
return 0;
}

Editorialist's Solution
#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;
}

9 Likes

Editorial Solution
(ans[n-2] ^ temp) == ans[n-1]

How we will know: ans[i]^temp==ans[n-1]

3 Likes

I followed a seemingly different approach for the problem.
a) The basic idea used if we take bitwise xor of four numbers of the type 4N , 4N+1,4N+2,4N+3 it will always turn out to be zero.

b) we can represent a set of four elements by a number i as 4i, 4i+1, 4i+2,4i+3

c) for any number a , floor(a/4 )(conventional division in c++) is bound to form that 4 element set which contains the number a. We will not take this number in our set of iβs as we simply have sufficiently possible iβs to sufficiently fill the array.

So one can look at the array of size N in the following way:

1. if N%4==1 , we simply fill the first element of the array with X and for starting from i =0 we store all possible iβs 0,1,2β¦ b such that size of this set is n/4 (not including X/4);

2. if N%4==2 then always 0,X is the possible pair to include . form a n/4 sized set of iβs which do not include 0,X/4;

Now the tricky part of N%4==3 and ==0 comes.
find the binary representation of X. All possible values of X can be represented in 19 bit size.

1 Like
1. if N%4 == 3
we need to find three numbers a,b,c such that a^b^c = X.
3 cases arise:
i) 3 or more set bits:
a = 2**(i1) , b = 2**(i2) , c = X-a-b where i1,i2 are the 1st and 2nd bit position which are set.
ii) 2 bits are set:
a = 0 , b = 2**(i1) , c = 2**(i2) where i1,i2 are 1st,2nd set bits.
iii) only 1 bit is set:
if we take a = 0, b =0 , c = 2**(i1) duplicity arises. Two remove this we simply find j1 and j2 which are the 1st and 2nd bit positions not being set. we can modify a,b,c as:
a = 2**(j1) , b = 2**(j2) , c = 2**(i1)+a+b , j1 and j2 bit positions appear 2 times there contribution during bitwise xor becomes 0.

now simply omit a/4 , b/4 , and c/4 from the set of iβs of size N/4.

1. finally N%4==0 :
we need a,b,c,d 4 numbers gosh! but still it isnβt tough if properly thought of.
cases:
i) if X has 4 or more set bits:
simply a,b,c become 2 to powers i1,i2,i3 ; d = X-a-b-c
ii) 3 set bits:
a = 0, b,c,d are 2 raised to powes i1,i2,i3 respectively.
iii) 2 set bits:
we find j1,j2 as described in case N%4==3 and a = 2**(j1), b = 2**(j2) , c= a+2**(i1), d = b+2**(i2)
iv) only 1 set bit:
find j1,j2,j3 3 non-set bit positions and now a,b,c,d become:
a= 2**(j1) , b = 2**(j2) , c = 2**(j3) , d = 2**(i1) +a+b+c;

in this case we need iβs set of size N/4 -1 with no i equal to a/4,b/4,c/4 or d/4.

Finally for all possible values of i include the four element set in the array and you have your answer

1 Like

https://www.codechef.com/viewsolution/56199402
can anyone check why itβs partially correct?

yes bro i used the same approach but got wrong answer. Can anyone please verify the code from @codechef team.

using namespace std;

int main()
{
long int T;
cin>>T;
while(Tβ){
long long int x,n;
cin>>n>>x;
if(n>4)
{
long long int l=n;
for(long long int i=4;i<l;i=i+4){
if(i!=(x-x%4))
cout<<i<<" β<<i+1<<β β<<i+2<<β β<<i+3<<β β;
else l=l+4;
}
}
if(n%4 == 0) cout<<1<<β β<<2<<β β<<3<<β β<<x<<β\n";
else if(n%4 == 1) cout<<x<<"\n";
else if(n%4 == 2) cout<<0<<" β<<x<<β\n";
else if(n%4 == 3) {
long long int h=x-x%4;
if(h !=x)
cout<<h<<" β;
if(h+1 != x)
cout<<h+1<<β β;
if(h+2 != x)
cout<<h+2<<β β;
if(h+3 != x)
cout<<h+3<<β β;
cout<<β\n";
}

}
return 0;
}

In your code if X is less than n then X is surely repeated in your array. First find the elements of n%4 which xor to X and then sets of four which do not include the elements calculated for n%4;

1 Like

if(i!=(x-x%4))
cout<<i<<" β<<i+1<<β β<<i+2<<β β<<i+3<<β β;
else l=l+4;

I have used this code if(i!=(x-x%4)) not to repeat the x in array.

at x = 500000 , if you print h+i , i = {1,2,3} it is going to exceed the limit of 0<=a<=500000 where a is an element of the array.

1 Like

Thanks

But my code is not also showing partialy correct one (30% result) where x can be max 10^5 .

please tell me the second and third condition in this

#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;


}

Isnβt it funny that the logic conclusively was just x^x=0

I used the exact same approach of video editorial but in c++14 it is giving some WA
While same code on c++17 passed, What could be the reason?

#include <iostream>
using namespace std;

void print_arr(int ar[], int n)
{
for(int i=0;i<n;i++)
cout<<ar[i]<<" ";
cout<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
{
int N, X;
cin>>N>>X;

if(N == 1)
{
cout<<X<<endl;
continue;
}
int ans[N];
int temp_xor = 0;
for(int i=0;i<=N-2;i++)
{
ans[i] = i;
temp_xor = temp_xor ^ i ;
}
int last = temp_xor ^ X;
int setbit_18 = (1LL<<18) ;

if(last >= N-1 && last <= 500000)
ans[N-1] = last;
else
{
ans[N-1] = last ^ setbit_18 ;
if(ans[N-1] == (ans[0]^setbit_18))
ans[1] = ans[1] ^ setbit_18;
else
ans[0] = ans[0] ^ setbit_18;
}
print_arr(ans, N);
}
return 0;
}



I think binary representation of 5*105 will have 19 bits in binary representation not 18. @notsoloud

Please link to the WA C++14 submission and the AC C++17 submission

Edit:

If itβs this vs this, note that the code is not the same (the former gives this honking great warning:

[simon@simon-laptop][16:32:05]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling lredoc-XORED-wa.cpp
Executing command:
g++ -std=c++17 lredoc-XORED-wa.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
lredoc-XORED-wa.cpp: In function βint main()β:
lredoc-XORED-wa.cpp:41:25: warning: suggest parentheses around comparison in operand of β^β [-Wparentheses]
41 |             if(ans[N-1] == ans[0]^setbit_18)
|                ~~~~~~~~~^~~~~~~~~
Successful


)

Got it. Thanks for the effort.

1 Like

@ssjgz Can you please confirm the mistake in the editorial.

Thanks a lot for pointing out! Hope it is fine now!

2 Likes

Thanks for updating the editorial. However, there is one more point. Z will still be less than 219, since the maximum number we can get with 19 bits is 219 - 1. @notsoloud

1 Like
#include <bits/stdc++.h>
using namespace std;
#define int     int64_t
#define IOS     ios::sync_with_stdio(0); cin.tie(0);

signed main() {
IOS;
int t; cin >> t;
const int M = 32;
int even = 4e5, odd = 4e5+1, zero = 0;
int even_two = 400000, odd_two = 400002;
int inf = 5e5+1;
while(t--) {
int n, x; cin >> n >> x;
cout << n << " " << x << "\n";
if(n == 1) {
cout << x << "\n";
} else if(n == 2) {
cout << 0 << " " << x << "\n";
} else {
set<int> ans;
int till = 0;
for(int i=1;i<=n-1;i++) {
// ans.insert(i);
till = till ^ i;
}
// n - 1 elements filled till here [1, 2, 3, ... n - 1]
int last = x ^ till;
// last ^ till = x; last = x ^ till;
// if last belongs to [1, 2, 3, ... n - 1]
if((last > 0) && (last < n)) {
auto it = ans.find(last);
if(last == 1) {
// don't want 1 in the array as [2 ^ 3 ^ ... ^ n - 1] = X
// erase 1 and 2
ans.erase(it);
// till = till ^ 1;
// till = till ^ 2;
// add three unique elements such that
ans.insert(even_two);
ans.insert(odd_two);
ans.insert(zero);
// till = till ^ even_two;
// till = till ^ odd_two;
// till = till ^ zero;
} else {
// don't want some number which is greater than one
ans.erase(it);
ans.erase(ans.begin());
// till = till ^ last;
// till = till ^ 1;
ans.insert(even);
ans.insert(odd);
ans.insert(zero);
// till = till ^ even;
// till = till ^ odd;
// till = till ^ zero;
}
} else {
if(last < inf) {
ans.insert(last);
till = till ^ last;
} else {
auto it = ans.upper_bound(last);

}
}

// int i = 0;
// cout << "SIZE: " << ans.size() << "\n";
// for(auto num : ans) {
//     cout << i + 1 << " " << num << "\n";
//     i += 1;
// }
// till = 0;
// for(auto num : ans) {
//     till = till ^ num;
// }
cout << "XOR: " << till << "\n";

// assert(ans.size() == n);
assert(till == x);

// for(auto num : ans) {
//     cout << num << " ";
// }
// cout << "\n";
}
}
}


It passes all the test cases for the first subtask but fails on every test case of the second subtask. I tried to debug for a very long time but couldnβt figure out the problem. What am i missing here?