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.