MEX with XOR

1. MEX after deleting one element

Let $m$ be the MEX of the entire array $A$. Every value from $0$ to $m-1$ occurs, and $m$ does not occur.

Deleting $A_i$ gives two cases:

• If $A_i<m$ and $A_i$ occurs exactly once, then $M_i=A_i$.

Consequently, the positions with $B_i=0$ are exactly the positions containing a value below $m$ that occurs once. At every position with $B_i\ne0$, we must have

$$A_i=B_i\oplus m,$$

where $\oplus$ denotes bitwise XOR.

Let $Z$ be the number of zeros in $B$, and let $f(v)$ be the frequency of a positive value $v$ in $B$. Once $m$ is fixed, all positions with nonzero are determined.

If one of their resulting values below $m$ occurs exactly once, the candidate is impossible: that position would have to produce $B_i=0$. Values occurring at least twice cause no problem. The remaining missing values below $m$ can be assigned, one each, to the zero positions of $B$.

Thus, a candidate $m$ is feasible if and only if:

• For every positive $v$ with $v\oplus m<m$, we have $f(v)\ne1$.

Since $m$ is the MEX of an array of length $N$, we have $0\le m\le N$.

2. Small inputs: enumerate the MEX

Try every $m=0,1,\cdots,N$. Set $A_i=B_i\oplus m$ at nonzero positions and fill zero positions with the missing values below . If the number of missing values is not , this candidate is impossible.

We can then delete each position in turn and recompute its MEX directly. Checking one candidate takes $O(N^2)$ time, giving an $O(N^3)$ algorithm for subtask 3.

Using the necessary and sufficient conditions above is faster. For each candidate, count the frequencies of values below $m$, check that none occurs once, and check that exactly $Z$ values are missing. Each candidate takes $O(N)$ time, yielding an $O(N^2)$ algorithm for subtask 4.

3. Reduce XOR comparisons to the highest set bit

Let $h$ be the position of the highest set bit of a positive value $v$. The numbers $v\oplus m$ and $m$ agree at every higher bit and differ at bit $h$. Therefore,

$$v\oplus m<m \quad\Longleftrightarrow\quad \text{bit }h\text{ of }m\text{ is }1.$$

Group the positive values in $B$ by their highest set bit. For each bit $h$, compute:

• $C_h$, the number of distinct positive values whose highest set bit is $h$.
• Whether the group contains a value that occurs exactly once.

If the group contains a value occurring once, bit $h$ cannot be set in $m$. Selecting it would produce a unique value below $m$ at a nonzero position.

Exclude these forbidden bits, and let $s_h$ indicate whether bit $h$ is selected. The number of distinct values below $m$ already provided by nonzero positions is $\sum_h C_hs_h$. Hence

$$Z=m-\sum_h C_hs_h=\sum_h(2^h-C_h)s_h.$$

For each allowed bit, define a weight

$$W_h=2^h-C_h.$$

We need to select a subset of the allowed bits whose weights sum to $Z$.

There are exactly $2^h$ positive integers with highest set bit $h$. Thus, $C_h\le2^h$ and every weight is nonnegative.

4. Subset-sum DP and reconstruction

Let $dp[s]$ indicate whether a subset of the processed bits has total weight $s$. Initially, only $dp[0]$ is true.

For each allowed bit with positive weight $W_h$, process $s=Z,Z-1,\cdots,W_h$ and update

$$dp[s]\leftarrow dp[s]\lor dp[s-W_h].$$

Descending order prevents selecting the same bit more than once. Whenever a state is reached for the first time, record its previous sum and the selected bit so that the choices can be reconstructed.

A zero-weight bit can be omitted without changing the sum, so skip it. Weights larger than $Z$ can also be skipped.

If $dp[Z]$ is false, print -1. Otherwise, reconstruct $m$ from the selected bits and construct $A$:

• At every nonzero position, set $A_i=B_i\oplus m$.
• Find the values from $0$ to $$ that have not appeared.

5. Correctness proof

For any valid answer with MEX $m$, the first observation implies that no forbidden bit is selected and that the selected weights sum to $Z$. Therefore, if an answer exists, the DP can reach $Z$. Omitting zero-weight bits preserves the sum, so skipping them is safe.

Conversely, consider the value $m$ reconstructed by the DP. Every distinct positive value in a selected group occurs at least twice. Let $D$ be the total number of these distinct values. Then

$$m=Z+D\le Z+\frac{N-Z}{2}\le N.$$

Thus, the reconstructed value is within the possible MEX range.

At a nonzero position, $A_i$ cannot equal $m$, since that would imply $B_i=0$. These positions provide exactly distinct values below , each occurring at least twice. Assign the remaining values to the zero positions, one each.

The completed array contains every value below $m$ and does not contain $m$, so its MEX is $m$. A zero position contains a unique value below $m$, making the MEX after deletion equal to that value. Deleting a nonzero position leaves the MEX equal to $m$. Both cases satisfy the required XOR equation.

Finally, $m\le N<2^{30}$ and $B_i<2^{30}$ imply . The missing values are smaller than , so every output value is within the allowed range.

6. Special-case subtasks

In subtask 1, every $B_i>0$. Set $A=B$. Since zero is absent, the MEX remains zero after any deletion. This gives an $O(N)$ solution.

In subtask 2, every $B_i$ is either zero or one. If all values are zero, any permutation of $0,1,\cdots,N-1$ works. Otherwise, a solution exists if and only if $Z$ is even.

To prove this, consider the value $m\oplus1$ assigned to every position with $B_i=1$. If $m$ is even, this value is $m+1$, so every value below must come from a zero position and . If is odd, the value is . A single occurrence is impossible, while at least two occurrences imply . Both cases require even .

For even $Z$, choose $m=Z$. Assign $0,1,\cdots,Z-1$ to the zero positions and $Z+1$ to the one positions. This construction takes time.

7. Complexity

Sorting the positive input values gives their frequencies and the per-bit information in $O(N\log N)$ time. There are 30 possible highest-bit positions, so the DP takes $O(30Z)$ time. Reconstructing the answer takes $O(N)$ time.

The total time complexity is $O(N\log N+30Z)$, and the space complexity is $O(N)$. The total bound of $200\,000$ on $N$ across all test cases makes this sufficient for the full constraints.

Solution written by GPT