Учитывая N целых чисел, удалите 1 из них так, чтобы их XOR был как можно большим - PullRequest
Новая
       23

Учитывая N целых чисел, удалите 1 из них так, чтобы их XOR был как можно большим

0 голосов
/ 28 марта 2020

Вам дается N 64-разрядных целых чисел (или длинных длинных). Вам нужно удалить одно из этих значений, чтобы XOR этих N-1 (все они без того, который был удален) был как можно большим. Распечатайте XOR в консоли. Число целых чисел не будет превышать 1e6.

Под XOR всех целых чисел я имею в виду что-то вроде этого: 

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

Кроме того, это не моя домашняя работа . Я знаю, что размещение домашней работы здесь не одобряется. Я пытался решить это сам, но я только придумал решения, которые работают в O (n ^ 2).

Ответы [ 3 ]

1 голос
/ 28 марта 2020

(Интеллектуальное) грубое принуждение может быть лучшей вещью. И вам даже не понадобится O(n²) для этого.

Поскольку xor обратим, вы можете сначала вычислить xor для всех чисел и снова xor с одним числом, чтобы получить xor для всех, кроме этого числа.

Используя это, довольно просто уменьшить решение о грубой силе до 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];
}
1 голос
/ 28 марта 2020

Существуют и другие ответы, показывающие, как это можно сделать за 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).

1 голос
/ 28 марта 2020 
#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;
}
...