Given N integers, remove 1 of them so that their XOR is as large as possible

Question

You are given N 64-bit integers (or long longs). You need to remove one of then so that the XOR of those N-1 (all of them without the one that has been removed) integers, is as large as possible. Print out the XOR in the console. The number of integers will not exceed 1e6.

By XOR of all the integers I mean something like this:

long long myXor=0;
for(int i = 0;i<arr.size();i++){
     myXor=xor(myXor,arr[i]);
}

Also, this is not my homework. I know posting homework here is frowned upon. I've been trying to solve this my self, but I've only come up with solutions that work in O(n^2).

Hint: The opposite of xor is xor (i.e., `(a ^ b ^ c ^ d) ^ a = b ^ c ^ d` and `(a ^ b ^ c ^ d) ^ b = a ^ c ^ d`). An O(n) solution exists. — Artyer, Mar 28 '20 at 12:10
@Artyer Oh, that's a very good hint. I knew the solution would have to involve the reverse of XOR, but found that it is XNOR. It did not work, though. — StLuke5, Mar 28 '20 at 12:12

Aplet123 · Answer 1 · 2020-03-28T14:58:38.553

1

#include <iostream>
#include <limits.h>

typedef long long ll;

const int MAX_N = 1000000;

int main() {
    // initialize the total xor
    ll tot = 0;
    // static allocation is faster :)
    ll nums[MAX_N];
    // read in the number of elements
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i ++) {
        std::cin >> nums[i];
        // use the built in xor operator (^)
        tot ^= nums[i];
    }
    // initialize the maximum value to the smallest possible long
    ll maxVal = LONG_LONG_MIN;
    for (int i = 0; i < n; i ++) {
        // xor undos itself so this is essentially removing nums[i]
        ll val = tot ^ nums[i];
        // if it's larger than the max then update the max
        if (val > maxVal) {
            maxVal = val;
        }
    }
    // output it
    std::cout << maxVal << std::endl;
}

edited Mar 28 '20 at 14:58

answered Mar 28 '20 at 12:14

Aplet123

33,825
1
29
55

Thank You very much, I've just come up with the same solution as You, thanks to the hint I was given. – StLuke5 Mar 28 '20 at 12:15
Some tips: Don't use `` or `using namespace std;` in a real program: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice . Avoid `#define` when possible: `using ll = long long; const unsigned int MAX_N = 1000000;` – aschepler Mar 28 '20 at 14:55

score 1 · Answer 2 · answered Mar 28 '20 at 12:15

(Intelligent) brute-forcing might actually be the best thing. And you won't even need O(n²) for that.

Since xor is reversible you can calculate the xor of all numbers first and xor again with one number to get the xor of all except that number.

Using this it is quite easy to reduce the brute-force solution to O(n):

long long xorAll = 0;
for(int i = 0;i<arr.size();i++){
     xorAll = myXor^arr[i];
}
long long max = LONG_LONG_MIN; // Store the maximum number.
for(int i = 0; i < arr.size(); i++) {
    if((xorAll^arr[i]) > max)
        max = xorAll^arr[i];
}

cigien · Answer 3 · 2020-03-28T16:37:52.893

There are other answers showing how this can be done in O(n) time quite easily, e.g.

// 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);
}

However, you can use the property that the xor operations can be done out of order. This lets you use the reduce function in numeric, like so

// 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);

Here is a quick and dirty comparison between the 2 solutions, that show a considerable speedup (about 40% for 1e6 numbers).

Given N integers, remove 1 of them so that their XOR is as large as possible

3 Answers3