XOREQUAL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

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;
    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);
        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());}

    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()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                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:

2 Likes

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!

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
	{
		Reader sc=new Reader();
		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

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

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