XOREQUAL - Editorial

editorial
, , ,
3

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
4

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

5

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
6

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
7

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

8

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

1 Like
9

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

10

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
11

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

12

Thanks!

13

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=(resulta)%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;

}

14

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

}

}

15

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

1 Like
16

can u share your submission.

17

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

18

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((1LLk*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";
}

}

19

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

20

Where did you get this formula from?

21

Experimentation. Like I don’t think I have seen a list of such useful formulas anywhere; although it woud be nice if such a list existed.

22

i saw the solution from the video editorial and I didn’t understand one thing what’s the use of %MOD like he is storing double of previous answers
That is if n = 4, so it is storing ans[3] × 2 at n = 4
Ans of n = 4 is …4× 2 = 8. I don’t get what’s the use of MOD here? like there was given in the Q to use 10^9+7 since the input were larget but what is the use of MOD in this line ?
" ans[i] = (ans[i-1]*2)% MOD; "
#include

#include

#include

#include

using namespace std;

const int MX = 1e5 + 5; //since in Q it is given at max it will go it here

const int MOD = 1e9 + 7;

vectorans(MX);

void pre(){

ans[1]=1;              
for(int i=2; i<MX; i++)     

    ans[i] = (ans[i-1]*2)% MOD;

}

int main(){

pre();

int t;cin>>t;  

while(t--){

    int n; cin>>n;

    cout<<ans[n]<<endl;

}

return 0;

}