XOREQUAL - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh






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.


  • 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.


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.


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


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;
        int n; cin >> n;
        cout << dp[n - 1] << endl;
Tester's Solution
import java.util.*;
import java.io.*;
class Main{
    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{
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
    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());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));

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

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

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


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


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;   
             return (x*halfPower*halfPower)%1000000007;  
	public static void main (String[] args) throws java.lang.Exception
		Reader sc=new Reader();
		long t=sc.nextLong();
		while(t-- >0){
		    long n=sc.nextLong();

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


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

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!

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

Python solution with bit shift

mod = 10**9+7
for _ in range(input()):
n = input()
print n
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


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).
using namespace std;

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

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


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;


return res;


int main() {
int t;
ll i,count=0;
int n;
ll end=expo(n-1);




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

1 Like

can u share your submission.

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 ??

using namespace std;

const int mod = 1e9 + 7;

long long int power(int a,int b,int mod)
return 1;

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

int main()

int t;
    int n;
    long long int ans=power(2,n,mod);


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?