ค่า XOR สูงสุดของทุกองค์ประกอบในอาร์เรย์กับอีกอาร์เรย์หนึ่งใน C++

บทนำ

ในปัญหานี้ เราได้รับอาร์เรย์ A และ B จำนวน n องค์ประกอบแต่ละอัน ภารกิจคือสร้างโปรแกรมหาค่า XOR สูงสุดที่เป็นไปได้ของทุกองค์ประกอบในอาร์เรย์หนึ่งกับอีกอาร์เรย์หนึ่ง

เราต้องคำนวณ XOR สูงสุดสำหรับแต่ละองค์ประกอบของอาร์เรย์ A กับอาร์เรย์ B นั่นคือ สำหรับแต่ละองค์ประกอบของ A เราจะเลือกองค์ประกอบใน B ที่ให้ค่า XOR สูงสุด

ตัวอย่าง

อินพุต -

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

เอาต์พุต -

11 14 15 13

คำอธิบาย -

ลองดูการจับคู่ XOR ของแต่ละองค์ประกอบใน A กับทุกตัวใน B แล้วเลือกค่าสูงสุด:

3 XOR 8 = 11  3 XOR 2 = 1  3 XOR 4 = 7  3 XOR 1 = 2  Max = 11
6 XOR 8 = 14  6 XOR 2 = 4  6 XOR 4 = 2  6 XOR 1 = 1  Max = 14
11 XOR 8 = 3  11 XOR 2 = 9  11 XOR 4 = 15  11 XOR 1 = 10  Max = 15
9 XOR 8 = 1   9 XOR 2 = 11  9 XOR 4 = 13  9 XOR 1 = 8   Max = 13

วิธีง่ายๆ คือคำนวณทุกคู่ (Brute Force) ซึ่งมีความซับซ้อน O(n²) ไม่เหมาะสำหรับข้อมูลขนาดใหญ่

วิธีที่ดีกว่าคือใช้โครงสร้างข้อมูล Trie (Prefix Tree) เก็บค่า Binary ของทุกองค์ประกอบในอาร์เรย์ B เพื่อจับคู่กับ A เพื่อหา XOR สูงสุด

สำหรับองค์ประกอบใน A เราจะตรวจสอบบิตสำคัญที่สุด (MSB) และพยายามทำให้เป็น 1 แล้วไปบิตถัดไป ตามนี้เราจะได้องค์ประกอบใน B ที่ให้ XOR สูงสุดสำหรับแต่ละตัวใน 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] = NULL;
    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 << "The maximum possible XOR of every possible element in array A with Array B is\n";
    for (int i = 0; i < N; i++)
        cout << findMaxXor(root, A[i]) << "\t";
    return 0;
}

ผลลัพธ์

The maximum possible XOR of every possible element in array A with Array B is
11 15 14 13

คำอธิบาย

Trie เก็บตัวเลขใน B เป็น Binary 32-bit เมื่อค้นหาสำหรับตัวเลขใน A จะพยายามเดินทางตรงข้ามกับบิตของตัวเลข (ถ้าบิตเป็น 0 พยายามไปทาง 1, ถ้า 1 พยายามไปทาง 0) เพื่อให้ XOR ได้ 1 ที่บิตนั้น ทำให้ได้ค่าสูงสุด

ความซับซ้อน: O(n × 32) ≈ O(n) ซึ่งเร็วกว่า Brute Force มาก