# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* wesam13

*satyam_343*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1688

# PREREQUISITES:

Observation

# PROBLEM:

You’re given an array A of length N.

It’s known that 2\cdot (A_1 \oplus A_2 \oplus \ldots \oplus A_N) \geq (A_1 \mid A_2 \mid \ldots \mid A_N).

Do the following N times:

- Choose an element x remaining in the array.
- Either create a new box and add x to it, or add x to an existing box whose XOR is at least x.

Find the minimum number of boxes needed.

# EXPLANATION:

Let’s make some observations.

Let B be the maximum bit present in some array element.

Let’s call some A_i *good* if it contains B.

Then, note that:

- No box can contain \geq 3 good elements.
- If a non-empty box contains only non-good elements, we can never insert a good element into it.
- If a box contains exactly one good element, we can insert as many non-good elements into it as we like.

## Proof

All three claims are fairly easy to prove once you’ve written them down.

- When the second good element is inserted into a box, the xor of this box no longer contains bit B; which means it only contains bits strictly smaller than B.

This means any good element is strictly larger than this XOR, and can no longer be inserted into it. - The second claim also follows from similar logic: with only non-good elements, any good element is strictly larger than their XOR since only bits less than B are used.
- The third claim is similar: with exactly one good element, the XOR will contain B.

This makes it strictly larger than any non-good element, so any such element can always be inserted.

So, suppose there are k good elements in the array.

Then, notice that we surely need at least \left \lceil \frac{k}{2} \right\rceil boxes; since each box can contain at most 2 good elements.

If k were odd, using exactly \left \lceil \frac{k}{2} \right\rceil boxes is possible, as follows:

- Keep one good element aside, and pair the rest.
- Put the unpaired element into one box, and then all the non-good elements.
- Then, for each pair of good elements, put the larger one into a new box, then the smaller one.

Now, recall the condition 2\cdot (A_1 \oplus A_2 \oplus \ldots \oplus A_N) \geq (A_1 \mid A_2 \mid \ldots \mid A_N).

This really just means that B, the largest bit, is present in the XOR of all elements.

This is only possible when B occurs an odd number of times, i.e, the number of *good* elements is odd.

We’ve already solved the odd case, so we’re done!

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& p : a) cin >> p;
const auto get_max = [&](int num) -> int {
for (int bit = 60; bit >= 0; bit--) {
if ((1ll << bit) & num) return bit;
}
assert(false);
return -1;
};
int mx = 0;
for (const int& p : a)
mx = max(mx, get_max(p));
int cnt = 0;
for (const int& p : a)
if ((p & (1ll << mx)))
++cnt;
cout << ((cnt + 1) >> 1) << '\n';
}
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = max(a)
mxbit = 60
while x & (2 ** mxbit) == 0: mxbit -= 1
ct = 0
for i in range(n):
ct += a[i] >> mxbit
print((ct + 1)//2)
```