ค่า XOR สูงสุดของสองจำนวนในอาร์เรย์ใน C++

ให้อาร์เรย์ nums หาค่า ai XOR aj สูงสุด (0 ≤ i,j < n) ตัวอย่าง: [3,10,5,25,2,8] → 28 (จาก 5 XOR 25)

ขั้นตอนการแก้ปัญหา (Trie บิต)

1. สร้าง Trie บิต (32 ระดับ) ใส่ตัวเลขทุกตัว
2. สำหรับแต่ละตัวเลข x หาคู่ที่ให้ XOR สูงสุด:
   • เดินจากบิต MSB ถึง LSB
   • พยายามเดินทางตรงข้ามบิตของ x (ถ้าบิตของ x = 0 พยายามไปทาง 1) เพื่อให้ XOR ได้ 1
   • ถ้าไม่มีทางตรงข้าม เดินทางเดิม
   • สร้างคำตอบจากบิตที่เดินได้
3. คืนค่าสูงสุด

ตัวอย่างโค้ด C++

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

struct Node { Node* child[2]; Node() { child[0]=child[1]=nullptr; } };

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

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

Input

[3,10,5,25,2,8]

Output

28