 # SUBARRAYXOR - Editorial

Setter: Jeevan Jyot Singh
Tester: Manan Grover
Editorialist: Lavish Gupta

Easy

Bitwise Xor

# PROBLEM:

JJ is back with another challenge. He challenges you to construct an array A containing N integers such that the following conditions hold:

• For all 1 \le i \le N, 1 \le A_i \le 10^6
• Every subarray has non-zero XOR. That is, for every 1 \le L \le R \le N, A_L \oplus A_{L+1} \oplus \ldots \oplus A_R \ne 0. Here, \oplus denotes the bitwise XOR operation.

Can you complete JJ’s challenge?

Under the given constraints, it can be proved that there always exists at least one array satisfying these conditions. If there are multiple possible arrays, print any of them.

# QUICK EXPLANATION:

What if there is a subarray having XOR = 0?

If there is a subarray having XOR = 0, there will exist a pair of distinct values i, j such that the XOR of prefixes of length i and j will be equal.
Hence, if XOR of all prefixes are distinct, then there will be no subarray having XOR = 0.

Assigning XORs

So let us assign distinct positive XORs to each prefix length. One way can be to assign XOR_{[1, i]} = i.
This means that (i-1) \oplus A_i = i

# EXPLANATION:

\oplus_{[L, R]} denotes the XOR of the subarray starting at index L and ending at index R (inclusive).

Let’s say there exists a subarray [L, R] such that A_L \oplus A_{L+1} \oplus \ldots \oplus A_R = 0
Consider the XOR of the prefix [1 , L-1] and [1, R].

\oplus_{[1, R]} = (\oplus_{[1, L-1]}) \oplus (\oplus_{[L, R]}) \implies \oplus_{[1, R]} = \oplus_{[1, L-1]}

The above equation suggests that if there is a subarray having XOR = 0, there will exist a pair of distinct values i, j such that the XOR of prefixes of length i and j will be equal.

Hence, if XOR of all prefixes are distinct, then there will be no subarray having XOR = 0.

Now, there can be several ways in which we can assign the XOR values to each prefix length. One of the simplest way is to assign \oplus_{[1, i]} = i, i.e. for prefix of length i, let us assign it’s XOR value to be i.

Getting the array

So we have \oplus_{[1, i]} = i, \forall i: 1 \leq i \leq N
XOR of prefix of length one = 1 = A_1

Now, for a general index i > 1, \oplus_{[1, i]} = \oplus_{[1, i-1]} \oplus A_i
Substituting values, i = (i-1) \oplus A_i \implies A_i = (i-1) \oplus i

It can be proved that the above value of A_i ensures that A_i < 2\cdot i. Therefore,\forall i: 1 \leq i \leq N, A_i \leq 10^6

Bonus Problem

Suppose we modify the constraint of A_i, such that 1 \leq A_i \leq N. Can you construct an array now?

# TIME COMPLEXITY:

Assuming that taking XOR of two numbers is an O(1) operation, the above approach will take O(N) time for each testcase.

# SOLUTION:

Setter's Solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const int N = 1e5 + 5;

int ans[N];

void precompute()
{
ans = 1;
int cur = 1;
for(int i = 1; i < N; i++)
{
ans[i] = (cur + 1) ^ cur;
cur++;
}
}

void solve(int n)
{
for(int i = 0; i < n; i++)
cout << ans[i] << " ";
cout << endl;
}

int32_t main()
{
IOS;
precompute();
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
int n; cin >> n;
solve(n);
}
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i = 0; i < n; i++){
cout<<(i ^ (i + 1))<<" ";
}
cout<<"\n";
}
return 0;
}

Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std ;

const ll z = 1000000007 ;

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

int arr[n] ;
arr = 1 ;

for(int i = 1 ; i < n; i++)
{
int req_xor = i+1 ;
int req_ele = (req_xor ^ i) ;
arr[i] = req_ele ;
}

for(int i = 0 ; i < n ; i++)
{
cout << arr[i] << ' ';
}
cout << endl ;
return ;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t;
cin >> t ;
while(t--)
solve() ;

return 0;
}

5 Likes

Is array A should have distinct values? where are they mentioned in the problem statement?

NO it is not necessary

1 Like

During the contest, I didn’t even read that 1 \leq A_i \leq 10^6 and instead thought that it was 1 \leq A_i \leq N. My solution is as follows,

Consider the prefix XOR array of A. This array should not have duplicated elements or a zero. I will take the prefix array to be a permutation of 1, 2, \cdots N. The original array can be constructed from the prefix array as follows,

A_i = pref[i] \oplus pref[i-1]

Now it is needed that 1 \leq A_i \leq N. For that, one of the permutations of the prefix XOR array which works is the Gray Code. Here is my submission,

https://www.codechef.com/viewsolution/57131490

2 Likes

it doesn’t need to be specified because if we take same element twice we will end up with a subarray xor as 0 (3 xor 3 == 0 ) so i think it is one of the observation if i am not wrong

I dont think it’s necessary.
for example
n = 4
1 2 1 4

1 Like

Interesting, is there any other similar xor problems to practice ?

3 Likes

but it will be hard to print in that order because of we are dealing with bits any way thanks

Here is the solution for the bonus part (where it is required that 1<= Ai <= N

The idea is to start from the highest bit possible (= floor of log2(N)) and keep dividing the range say [s,e] (initially s = 0, e = N-1) in two halves - [s,mid-1] and [mid+1,e] and set the required bit of ans[mid] to 1, and then recurse on the 2 halves.

The reason this works is because no matter what subarray you take, it will always have atleast 1 bit position where no of set bits is exactly 1, because we are setting exactly 1 bit in each half of our range.

Submission

2 Likes

what if we take odd numbers having odd number of set bits then also answer should be correct?

like I am not getting this, xor prefix shud be different then what after that? how to create that type of array??