Xor Tree
Contest: Codeforces Round 683 (Div. 1, by Meet IT)
Difficulty rating: 2100
Tags: binary search, bitmasks, data structures, divide and conquer, dp, trees

For a given sequence of distinct non-negative integers $$$(b_1, b_2, \dots, b_k)$$$ we determine if it is good in the following way:

- Consider a graph on $$$k$$$ nodes, with numbers from $$$b_1$$$ to $$$b_k$$$ written on them.
- For every $$$i$$$ from $$$1$$$ to $$$k$$$: find such $$$j$$$ ($$$1 \le j \le k$$$, $$$j\neq i$$$), for which $$$(b_i \oplus b_j)$$$ is the smallest among all such $$$j$$$, where $$$\oplus$$$ denotes the operation of bitwise XOR (https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Next, draw an undirected edge between vertices with numbers $$$b_i$$$ and $$$b_j$$$ in this graph.
- We say that the sequence is good if and only if the resulting graph forms a tree (is connected and doesn't have any simple cycles).

It is possible that for some numbers $$$b_i$$$ and $$$b_j$$$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

You can find an example below (the picture corresponding to the first test case).

Sequence $$$(0, 1, 5, 2, 6)$$$ is not good as we cannot reach $$$1$$$ from $$$5$$$.

However, sequence $$$(0, 1, 5, 2)$$$ is good.

You are given a sequence $$$(a_1, a_2, \dots, a_n)$$$ of distinct non-negative integers. You would like to remove some of the elements (possibly none) to make the remaining sequence good. What is the minimum possible number of removals required to achieve this goal?

It can be shown that for any sequence, we can remove some number of elements, leaving at least $$$2$$$, so that the remaining sequence is good.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 200,000$$$) — length of the sequence.

The second line contains $$$n$$$ distinct non-negative integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the sequence.

Output format:
You should output exactly one integer — the minimum possible number of elements to remove in order to make the remaining sequence good.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Note that numbers which you remove don't impact the procedure of telling whether the resulting sequence is good.

It is possible that for some numbers $$$b_i$$$ and $$$b_j$$$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

Example input:
5
0 1 5 2 6

Example output:
1

Example input:
7
6 9 8 7 3 5 2

Example output:
2

Editorial:
Let's see when a sequence of length $$$n$$$ is good.
Since we have $$$n$$$ edges and two of them must coincide (the pair of numbers with the smallest $$$\oplus$$$), we will have at most $$$n-1$$$ edges so we only need to check if the graph will be connected.
Let's analyze each bit from highest to lowest:
• If we have only one number we can keep it.
• If all numbers have this bit on or off we can ignore this bit, because the $$$\oplus$$$ will give 0 in this bit.
• If there is only one number with this bit on(off), this number will be connected to some of the numbers with this bit off(on), for all other numbers the $$$\oplus$$$ will give 0 in this bit, so we can keep the only number with this bit on(off) and go to the next bit.
• If we have at least two numbers with this bit on and off, then all the edges will connect numbers with the same bit on(off), so the graph won't be connected, so we need to delete all numbers with this bit on(off) except at most one (Case 2 or 3).