Google Kickstart 2019 Round G The Equation

Author: Gao Date: 2019-11-02
Google Kickstart 2019 Round G The Equation

Google Kickstart 2019 Round G The Equation

The essential of the problem is to find the number $k$ that xor with each $A_i$ gives the largest number. As described in the statement the upper limit is $10^{15}$ which result the highest bit is $log_2{10^{15}} = 50$. We start from the highest bit and try to set 1 at every possible position if it is feasible. But first, we need to process the $A$ to find out the minimum sum of n lowest bits, so that having the bit set to one or zero we know in advance if we will result in an infeasible solution or no.

Pay Attention to 1LL << n and read carefully of each limit, for example: M < $10^{15}$.

Solution