Maximizar la ecuación XOR

Declaración del problema:

Dado un arreglo de n elementos y un entero k, encuentra un entero x en el rango [0, k] tal que la suma XOR(x) se maximice. Imprime el valor máximo de la ecuación.

XOR-sum(x) = (x XOR A1) + (x XOR A2) + (x XOR A3) + … + (x XOR AN)

Formato de entrada:

La primera línea contiene el entero N que denota el número de elementos en A.
La siguiente línea contiene un entero k que denota el valor máximo de x.
Cada línea i de las siguientes N líneas (donde 0 ≤ i ≤ N) contiene un entero que describe Ai.

Restricciones:
1 ≤ n ≤ 10^5
0 ≤ k ≤ 10^9
0 ≤ A[i] ≤ 10^9

Entrada de ejemplo:

3
7
1
6
3

Salida de ejemplo:

14

Explicación:

Xor_sum(4) = (4^1) + (4^6) + (4^3) = 14.

Este problema fue preguntado en el examen de requisitos de Infosys. Estaba revisando los exámenes anteriores y me encontré con este problema. Solo pude encontrar una solución de fuerza bruta que consiste en calcular la ecuación para cada x en el rango [0, k] e imprimir el máximo. Pero la solución no funcionará para las restricciones dadas.

Mi solución:

#include
using namespace std;
int main()
{
int n, k, ans = 0;
cin >> n >> k;
vector a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i <= k; i++) {
int temp = 0;
for (int j = 0; j < n; j++) {
temp += (i ^ a[j]);
}
ans = max(temp, ans);
}
cout << ans;
return 0;
}

Encontré la solución en un sitio web. No pude entender lo que hace el código, pero esta solución da respuestas incorrectas para algunos casos de prueba.

Desplázate hacia abajo hasta la pregunta 3.