Существуют и другие ответы, показывающие, как это можно сделать за O(n)
время довольно легко, например,
// xor all the numbers
long long myXor = 0;
for(auto n : arr) {
myXor ^= n;
}
// find the max
long long max = std::numeric_limits<long long>::min();
for(auto n : arr) {
max = std::max(max, myXor ^ n);
}
Однако вы можете использовать свойство, что операции xor могут выполняться не по порядку. Это позволяет использовать функцию reduce
в numeric
, например,
// xor all the numbers
auto myXor = std::reduce(arr.cbegin(), arr.cend(), 0ll, std::bit_xor{});
auto choose = [myXor] (auto max, auto n) { return std::max(max, myXor ^ n);};
// find the max
auto max = std::reduce(arr.cbegin(), arr.cend(),
std::numeric_limits<long long>::min(), choose);
Здесь - быстрое и грязное сравнение между двумя решениями, которое показывает значительное ускорение (около 40% для номеров 1е6).