# XOREQUAL - Editorial

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

Simple

None

# PROBLEM

For given N, find the number of integers x in range [0, 2^N-1] such that x \oplus (x+1) = (x+2) \oplus (x+3). Since the number of such x can be large, print modulo 10^9+7.

# QUICK EXPLANATION

• All even x in range [0, 2^N-1] satisfy above condition
• Number of even values in range [0, 2^N-1] is 2^{N-1} which can either be computed for all N or computed by binary exponentiation.

# EXPLANATION

Since XOR operation is involved, letâ€™s consider what happens bit by bit and compare LHS and RHS

The first bit of x \oplus (x+1) and (x+2) \oplus (x+3) is always 1. Hence, for all x, first bit remains same.

Analysing second bit, we can divide into four cases

• x \bmod 4 = 0, here both x and x+1 have second bit off, and x+2 and x+3 have second bit on. Hence, LHS matches RHS on second bit too.
• x \bmod 4 = 1, here both x+3 and x have second bit off, and x+1 and x+2 have second bit on. Hence, LHS matches RHS on second bit too.
• x \bmod 4 = 2, here both x+2 and x+3 have second bit off, and x and x+1 have second bit on. Hence, LHS matches RHS on second bit too.
• x \bmod 4 = 3, here both x+1 and x+2 have second bit off, and x+3 and x have second bit on. Hence, LHS matches RHS on second bit too.

Hence, for second bit as well, all x satisfy the condition.

Anaysing third bit, there are 8 cases. Since 3rd bit has a cycle of 8 numbers (3rd bit of N number is same as 3rd bit of N \bmod 8), these four numbers x, x+1 x+2 and x+3 shall be a continuous segment of sequence 0000111100001111....

Hence, at most one of the pairs (x, x+1), (x+1, x+2), (x+2, x+3) can have different third bit.

• Assuming x and x+1 have different third bit. Hence, x+2 and x+3 shall also have same third bit as x+1. LHS has third bit 1, but RHS has third bit 0. This is not a valid x.
• Assuming x+1 and x+2 have different thrid bit: Hence, third bit of LHS shall be 0 \oplus 0 = 0 and third bit of RHS is 1 \oplus 1 = 0. Hence, this is a valid x
• Assuming x+2 and x+3 have different third bit. Hence, x and x+1 shall also have same third bit as x+2. LHS has third bit 0, but RHS has third bit 1. This is not a valid x.
• In case all of x, x+1, x+2, x+3 have same third bit, this is a valid x.

Generalizing from above, we can prove that all even x are valid, while all odd x are invalid.

Hence, for a given N, the number of valid candidates is the number of even values in range [0, 2^N-1]. Since half of the elements are even, the required answer is 2^{N-1}

The number of valid x can be calculated for each N beforehand in array in O(N) time to answer queries in O(1), or we can compute the power using binary exponentiation in O(log(N)) time.

# TIME COMPLEXITY

The time complexity is O(MAX+T) or O(T*log(MAX)) per test case, wher MAX = 10^5 for given problem.

# SOLUTIONS

Setter's Solution
# include<bits/stdc++.h>

# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const int maxn = 1e5, maxt = 1e5;
const int mod = 1e9 + 7;
ll dp[maxn + 1];
int main()
{
dp[0] = 1;
for(int i = 1; i <= maxn; i++)dp[i] = dp[i - 1] * 2 % mod;
int t; cin >> t;
while(t--){
int n; cin >> n;
cout << dp[n - 1] << endl;
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class Main{
//SOLUTION BEGIN
long MOD = (long)1e9+7;
long[] pow2;
int MX = (int)1e5;
void pre() throws Exception{
pow2 = new long[1+MX];
pow2[0] = 1;
for(int i = 1; i<= MX; i++)pow2[i] = pow2[i-1]*2%MOD;
}
void solve(int TC) throws Exception{
pn(pow2[ni()-1]);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new Main().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}

Feel free to share your approach. Suggestions are welcomed as always.

2 Likes

Just use the formula x~ \oplus~x+1 = 2\cdot2^{v_2(x+1)}-1 and we are done!
Thanks to @blueflare99 to pointing out the error in the previous equation. That was a bad error, sorry!

3 Likes

Easy Java Solution

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

class Codechef
{
static long power(long x, long y){
if( y == 0)
return 1;
long halfPower = power(x, y / 2);
if (y % 2 == 0){
return (halfPower*halfPower)%1000000007;
}
else{
return (x*halfPower*halfPower)%1000000007;
}
}

public static void main (String[] args) throws java.lang.Exception
{
long t=sc.nextLong();
while(t-- >0){
long n=sc.nextLong();
System.out.println(power(2,n-1));
}
}
}

Just use the given formula in the question and use logarithmic power strategy to calculate and youâ€™ll get the answer

2 Likes

Very Good Solution for cpp. Totally blown how easy it was to remove TLE.

Sorry I did not understand the exponent part. What is v2?
And is this only for even numbers? Because if we do 7 XOR 8 it is 1111 which isnâ€™t a power of 2
Thanks

EDIT: Typo

1 Like

Hello, I canâ€™t seem to understand the continuous sequence 0000111100001111â€¦
I mean I canâ€™t understand the way the pattern is shown? is it grouped by 3 bits of x, x+1, x+2, x+3?

1 Like

If I do power(2,n) then divide it by 2 it gives wrong but power(2,n-1) works, why?
Like (2^n)/2 and 2^(n-1) are same but in some cases mismatch plz explain. Thanks!
@taran_1407

Thats due to modulo exponentiation. You are calculating (pow(2, n) % mod ) / 2, not pow(2,n)/2.

1 Like

Easy C++ Solution with modular exponent
https://www.codechef.com/viewsolution/46425264

Python solution with bit shift

mod = 10**9+7
for _ in range(input()):
n = input()
if(n==1):
print n
else:
print (2<<(n-2))%mod

1 Like

The notation v_2(x) is used to denote the maximum number d such that 2^d \mid x

Thanks!

This is a simple solution in c++:
After analysis for some test cases and some value of x and n. I came to the conclusion that finally the answer will always be 2 to the power of (n-1).
#include<bits/stdc++.h>
using namespace std;

int power(int a,int b){
if(b==0){
return 1;
}
long temp=power(a,b/2);
long result=(temptemp)%1000000007;
if(b%2==1){
result=(result
a)%1000000007;
}
return result%1000000007;
}

int main(){
int t,n;
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
int ans=power(2,n-1);

cout<<(ans%1000000007)<<endl;
}

return 0;

}

#include <bits/stdc++.h>

using namespace std;
#define ll long long
ll M=1000000007;
ll expo(ll n){
ll res=1,a=2;

while(n>0){
if(n&1){
res=(res*a)%M;
}

a=(a*a)%M;
n=n>>1;
}
return res;

}

int main() {
int t;
cin>>t;
while(tâ€“){
ll i,count=0;
int n;
cin>>n;
ll end=expo(n-1);
count=end;

cout<<count<<endl;

}

}

Beginnerâ€™s question: Calculating beforehand does not cause TLE, while calculating after taking input n causes TLE. Why?

1 Like

Its just because there can be 10^5 test cases, calculating for each test case would cause repetions hence tle.

can somebody tell why this code is not working ??

#include
using namespace std;

const int mod = 1e9 + 7;

long long int power(int a,int b,int mod)
{
if(b==0)
return 1;

int k=power(a,b/2,mod);
if(b%2==1)
return ((((1LLkk))a)%mod);
else return((1LL
k*k)%mod);
}

int main()
{

int t;
cin>>t;
while(t--){
int n;
cin>>n;
long long int ans=power(2,n,mod);
cout<<ans/2<<"\n";
}

}

broâ€¦i didnâ€™t get thisâ€¦can you please elaborateâ€¦i was having same problemâ€¦when i wrote n/2 it gave me WAâ€¦and then it gave me AC when i wrote n-1. Please explain me it would ve a great help.
~From Beginner

Where did you get this formula from?