XOR lớn nhất của hai số trong mảng trong C++

Mô tả bài toán

Cho mảng nums (0 ≤ nums[i] < 2^31). Tìm giá trị lớn nhất của nums[i] XOR nums[j].

Ví dụ: [3,10,5,25,2,8] → 28 (5 XOR 25 = 28).

Giải thuật Trie nhị phân (Prefix Trie)

1. Xây dựng Trie nhị phân 32-bit từ tất cả số trong mảng (từ bit cao đến thấp).
2. Với mỗi số, tìm trong Trie số cho XOR lớn nhất: tại mỗi bit, cố gắng đi nhánh ngược bit hiện tại (nếu có).
3. Cập nhật kết quả lớn nhất.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

struct Node { Node* child[2] = {nullptr, nullptr}; };

class Solution {
    void insert(Node* root, int val) {
        for (int i = 31; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (!root->child[bit]) root->child[bit] = new Node();
            root = root->child[bit];
        }
    }
    int findMaxXor(Node* root, int val) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (root->child[!bit]) {
                ans |= (1 << i);
                root = root->child[!bit];
            } else {
                root = root->child[bit];
            }
        }
        return ans;
    }
public:
    int findMaximumXOR(vector<int>& nums) {
        Node* root = new Node();
        for (int x : nums) insert(root, x);
        int ans = 0;
        for (int x : nums) ans = max(ans, findMaxXor(root, x));
        return ans;
    }
};

int main() {
    vector<int> v = {3,10,5,25,2,8};
    Solution ob;
    cout << ob.findMaximumXOR(v); // 28
    return 0;
}

Độ phức tạp

• Thời gian: O(n * 32) ≈ O(n).
• Không gian: O(n * 32) cho Trie.