# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* raysh07

*sushil2006*

**Tester:***iceknight1093*

**Editorialist:**# 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)
```