Два элемента в массиве, xor которых является максимальным

Думаю, у меня есть алгоритм O(n lg U) для этого, где U - наибольшее число. Идея похожа на идею user949300, но с немного более подробной информацией.

Интуиция такова. Когда вы объединяете два числа вместе, чтобы получить максимальное значение, вы хотите иметь 1 в наивысшей возможной позиции, а затем из пар, которые имеют 1 в этой позиции, вам нужно объединить в пару с 1 в следующей возможное наивысшее положение и т. д.

Итак, алгоритм следующий. Начните с поиска самого высокого 1 бита в любом месте чисел (вы можете сделать это вовремя O(n lg U), выполнив O(lg U) работу для каждого из n чисел). Теперь разделите массив на две части - одно из чисел с 1 в этом бите и группу с 0 в этом бите. Любое оптимальное решение должно сочетать число с 1 в первом месте с числом с 0 в этом месте, поскольку в этом случае бит 1 будет максимально высоким. Любая другая пара имеет там 0.

Теперь рекурсивно мы хотим найти пару чисел из группы 1 и 0, которая имеет наивысшее значение 1. Для этого из этих двух групп разделите их на четыре группы:

• Числа, начинающиеся с 11
• Числа, начинающиеся с 10
• Числа, начинающиеся с 01
• Числа, начинающиеся с 00

Если есть какие-либо числа в группе 11 и 00 или в группах 10 и 01, их XOR будет идеальным (начиная с 11). Следовательно, если какая-либо из этих пар групп не пуста, рекурсивно вычислите идеальное решение из этих групп, а затем верните максимальное из этих решений подзадач. В противном случае, если обе группы пусты, это означает, что все числа должны иметь одну и ту же цифру во второй позиции. Следовательно, оптимальный XOR числа, начинающегося с 1, и числа, начинающегося с 0, в конечном итоге приведет к отмене следующего второго бита, поэтому мы должны просто взглянуть на третий бит.

Это дает следующий рекурсивный алгоритм, который, начиная с двух групп чисел, разделенных их старшим битом, дает ответ:

• Given group 1 and group 0 and a bit index i:
  • If the bit index is equal to the number of bits, return the XOR of the (unique) number in the 1 group and the (unique) number in the 0 group.
  • Создайте группы 11, 10, 01 и 00 из этих групп.
  • Если группа 11 и группа 00 непусты, рекурсивно найдите максимальное значение XOR для этих двух групп, начиная с бита i + 1.
  • Если группа 10 и группа 01 непусты, рекурсивно найдите максимальное значение XOR для этих двух групп, начиная с бита i + 1.
  • Если любая из вышеперечисленных пар была возможна, то верните максимальную пару, найденную рекурсией.
  • В противном случае все числа должны иметь один и тот же бит в позиции i, поэтому верните максимальную пару, найденную, посмотрев на бит i + 1 в группах 1 и 0.

Чтобы начать алгоритм, вы можете просто разделить числа из исходной группы на две группы - числа с MSB 1 и числа с MSB 0. Затем вы запускаете рекурсивный вызов вышеуказанного алгоритма с двумя группами чисел.

В качестве примера рассмотрим числа 5 1 4 3 0 2. У них есть представления

101  001  100   011   000   010

Начнем с разделения их на группу 1 и группу 0:

101  100
001  011  000  010

Теперь применим описанный выше алгоритм. Мы разбиваем это на группы 11, 10, 01 и 00:

11:
10:  101  100
01:  011  010
00:  000  001

Теперь мы не можем соединить какие-либо 11 элементы с 00 элементами, поэтому мы просто рекурсивно используем группы 10 и 01. Это означает, что мы создаем группы 100, 101, 010 и 011:

101: 101
100: 100
011: 011
010: 010

Теперь, когда мы подошли к корзинам с одним элементом в них, мы можем просто проверить пары 101 и 010 (что дает 111) и 100 и 011 (что дает 111). Здесь работает любой вариант, поэтому мы получаем, что оптимальный ответ 7.

Давайте подумаем о времени работы этого алгоритма. Обратите внимание, что максимальная глубина рекурсии равна O(lg U), поскольку в числах всего O(log U) бит. На каждом уровне дерева каждое число появляется ровно в одном рекурсивном вызове, и каждый из рекурсивных вызовов действительно работает пропорционально общему количеству чисел в группах 0 и 1, потому что нам нужно распределить их по битам. Следовательно, в дереве рекурсии есть O(log U) уровень, и каждый уровень выполняет O(n) работу, что дает общую работу O(n log U).

Надеюсь это поможет! Это была потрясающая проблема!

Это можно решить за O(NlogN) временную сложность с помощью Trie.

• Постройте дерево. Для каждого целочисленного ключа каждый узел дерева будет содержать каждый бит (0 или 1), начиная с самого старшего бита.
• Now for each arr[i] element of arr[0, 1, ..... N]
  • Perform query to retrieve the maximum xor value possible for arr[i]. We know xor of different type of bits(0 ^ 1 or 1 ^ 0) is always 1. So during query for each bit, try to traverse node holding opposite bit. This will make that particular bit 1 result in maximizing xor value. If there is no node with opposite bit, only then traverse the same bit node.
  • После запроса вставьте arr[i] в trie.
  • Для каждого элемента отслеживайте максимальное возможное значение Xor.
  • Во время прохождения каждого узла создайте другой ключ, для которого Xor максимизируется.

Для N элементов нам нужен один запрос (O(logN)) и одна вставка (O(logN)) для каждого элемента. Таким образом, общая временная сложность равна O(NlogN).

Вы можете найти красивое графическое объяснение того, как это работает в этой теме .

const static int SIZE = 2;
const static int MSB = 30;
class trie {
private:
    struct trieNode {
        trieNode* children[SIZE];
        trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                children[i] = nullptr;
            }
        }
        ~trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                delete children[i];
                children[i] = nullptr;
            }
        }
    };
    trieNode* root;
public:
    trie(): root(new trieNode()) {
    }
    ~trie() {
        delete root;
        root = nullptr;
    }

    void insert(int key) {
        trieNode* pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(!pCrawl->children[bit]) {
                pCrawl->children[bit] = new trieNode();
            }
            pCrawl = pCrawl->children[bit];
        }
    }

    int query(int key, int& otherKey) {
        int Xor = 0;
        trieNode *pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(pCrawl->children[!bit]) {
                pCrawl = pCrawl->children[!bit];
                Xor |= (1 << i);
                if(!bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
            } else {
                if(bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
                pCrawl = pCrawl->children[bit];
            }
        }
        return Xor;
    }
};

pair<int, int> findMaximumXorElements(vector<int>& arr) {
    int n = arr.size();
    int maxXor = 0;
    pair<int, int> result; 
    if(n < 2) return result;
    trie* Trie = new trie();
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse
    for(int i = 0; i < n; i++) {
        int elem = 0;
        int curr = Trie->query(arr[i], elem);
        if(curr > maxXor) {
            maxXor = curr;
            result = {arr[i], elem};
        }
        Trie->insert(arr[i]);
    }
    delete Trie;
    return result;
}

Игнорируя знаковый бит, одно из значений должно быть одним из значений с установленным наивысшим значащим битом. Если этот бит не установлен для всех значений, в этом случае вы переходите к следующему старшему значащему биту, который не установлен во всех значениях. Таким образом, вы можете сократить возможности для 1-го значения, посмотрев на HSB. Например, если возможности

0x100000
0x100ABC
0x001ABC
0x000ABC

Первое значение максимальной пары должно быть 0x100000 или 0x10ABCD.

@internal Server Error Я не думаю, что самое маленькое обязательно правильно. У меня нет отличной идеи для уменьшения второго значения. Любое значение, которого нет в списке возможных 1-го значения. В моем примере 0x001ABC или 0x000ABC.

Очень интересная задача! Вот моя идея:

• Сначала постройте двоичное дерево из всех чисел, используя двоичное представление, и сначала отсортируйте их по старшему разряду дерева (добавьте ведущие нули, чтобы соответствовать самому длинному числу). Когда это сделано, каждый путь от корня до любого листа представляет собой одно число из исходного набора.
• Пусть a и b являются указателями на узел дерева и инициализируют их в корне.
• Теперь переместите a и b вниз по дереву, пытаясь использовать противоположные ребра на каждом шаге, т.е. если a перемещается вниз по 0-ребру, b перемещается вниз по 1-ребру, если это невозможно.

Если a и b достигают листа, они должны указывать на два числа с «очень небольшим количеством» одинаковых битов.

Я только что придумал этот алгоритм и не знаю, верен ли он и как его доказать. Однако это должно быть во время работы O (n).

Создайте рекурсивную функцию, которая принимает в качестве аргументов два списка целых чисел, A и B. В качестве возвращаемого значения он возвращает два целых числа, одно от A и одно от B, которые максимизируют XOR для двух. Если все целые числа равны 0, вернуть (0,0). В противном случае функция выполняет некоторую обработку и дважды рекурсивно вызывает себя, но с меньшими целыми числами. В одном из рекурсивных вызовов он рассматривает выбор целого числа из списка A для передачи 1 в бит k, а в другом вызове он рассматривает выбор целого числа из списка B для передачи 1 в бит k.

У меня сейчас нет времени заполнять детали, но, может быть, этого будет достаточно, чтобы увидеть ответ? Кроме того, я не уверен, будет ли время выполнения лучше, чем N ^ 2, но, вероятно, будет.

Мы можем найти максимальное число за время O (n), а затем пройти через массив, выполняя xor с каждым элементом. Предполагая, что стоимость операции xor равна O (1), мы можем найти максимальное значение xor из двух чисел за время O (n).