PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Familiarity with bitwise XOR
PROBLEM:
Given an array A, count the number of integers X such that (X\oplus A_i) \lt A_i for all i.
EXPLANATION:
First, we analyze when exactly (X \oplus A_i) \lt A_i can happen.
Let’s look at a fixed bit.
- If X and A_i both don’t have it set, their XOR won’t have it set either - in particular it’ll be equal in both A_i and X\oplus A_i.
- If X and A_i both have it set, their XOR won’t have it set - meaning this is a bit which will be set in A_i but not in X\oplus A_i, which is good for us.
- If A_i has it set and X doesn’t, their XOR will have it set - meaning this bit will be equal in A_i and X\oplus A_i.
- If X has it set and A_i doesn’t, the XOR will have it set - meaning X\oplus A_i will have a bit that A_i doesn’t, which isn’t ideal.
So, only bits that are set in X matter to compare the XOR against A_i.
Further, it’s good for us if X and A_i both have some bit set.
In particular, consider the highest bit set in X, say b.
Then,
- If b is set in A_i as well, X\oplus A_i will definitely be less than A_i.
This is because A_i and X\oplus A_i can differ only in bits \leq b, and no matter how bits \lt b change, they cannot overcome a difference at the b-th bit since
2^0 + 2^1 + \ldots + 2^{b-1} \lt 2^b - If b is not set in A_i, the exact opposite applies: A_i will always be larger than X\oplus A_i.
So, X\oplus A_i is smaller than A_i if and only if the highest bit set in X is also set in A_i.
Now, we want X\oplus A_i to be smaller than A_i for every i.
So, the highest bit in X must be set in every A_i, meaning it must be set in the bitwise AND of all the A_i values.
Let P = A_1\ \&\ A_2\ \&\ \ldots\ \&\ A_N denote the bitwise AND of all the A_i.
The highest bit set in any valid X must also be set in P.
So, let’s instead fix a bit b that’s set in P, and count the number of valid X that have this as their highest bit set.
Note that once b is set in X, and nothing higher is set, the lower bits can be anything at all, since as we observed, lower bits won’t affect the inequality.
This means there are 2^b choices of lower bits once b is fixed.
So, the answer is simply the sum of 2^b across all b set in P.
You can compute this by iterating across all the bits - or notice that this sum is exactly the value P - after all, we’re exactly adding up the powers of 2 present in P's binary representation!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
vector <int> f(30, 0);
for (auto x : a){
for (int i = 0; i < 30; i++){
if (x >> i & 1){
f[i]++;
}
}
}
int ans = 0;
for (int i = 0; i < 30; i++){
if (f[i] == n){
ans += (1 << i);
}
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
AND = a[0]
for x in a: AND &= x
print(AND)