XOR tối đa của mỗi phần tử mảng A với mảng B trong C++

Cho 2 mảng A và B cùng kích thước n. Với mỗi phần tử của A, tìm phần tử trong B cho giá trị XOR lớn nhất.

Ví dụ

A = {3, 6, 11, 9}, B = {8, 2, 4, 1}

Kết quả: 11, 14, 15, 13

Giải pháp tối ưu: Trie nhị phân

Thay vì O(n²) so sánh tất cả cặp, xây Trie từ các số trong B (dạng nhị phân 32 bit). Với mỗi số trong A, duyệt Trie: tại mỗi bit, cố gắng đi nhánh ngược bit của A để XOR = 1 (tối đa).

Ví dụ minh họa

#include <iostream>
using namespace std;

struct trie {
    int value;
    trie *child[2];
};

trie* get() {
    trie* root = new trie;
    root->value = 0;
    root->child[0] = root->child[1] = NULL;
    return root;
}

void insert(trie* root, int key) {
    trie* temp = root;
    for (int i = 31; i >= 0; i--) {
        bool current_bit = key & (1 << i);
        if (temp->child[current_bit] == NULL)
            temp->child[current_bit] = get();
        temp = temp->child[current_bit];
    }
    temp->value = key;
}

int findMaxXor(trie* root, int element) {
    trie* temp = root;
    for (int i = 31; i >= 0; i--) {
        bool bits = element & (1 << i);
        if (temp->child[1 - bits] != NULL)
            temp = temp->child[1 - bits];
        else
            temp = temp->child[bits];
    }
    return (element ^ temp->value);
}

int main() {
    int A[] = {3, 11, 6, 9};
    int B[] = {8, 2, 4, 1};
    int N = sizeof(A)/sizeof(A[0]);
    trie* root = get();
    for (int i = 0; i < N; i++) insert(root, B[i]);
    cout << "Maximum XOR of each element in A with B:\n";
    for (int i = 0; i < N; i++) cout << findMaxXor(root, A[i]) << "\t";
    return 0;
}

Kết quả

11 15 14 13

Độ phức tạp: O(n × 32) ≈ O(n) thời gian, O(n × 32) không gian. Nhanh hơn nhiều so với O(n²).