ในปัญหานี้ เราจะได้รับสองอาร์เรย์ 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 Maximum = 11. 6 XOR 8 = 14 6 XOR 2 = 4 6 XOR 4 = 2 6 XOR 1 = 1 Maximum = 14. 11 XOR 8 = 3 11 XOR 2 = 9 11 XOR 4 = 15 11 XOR 1 = 10 Maximum = 15. 9 XOR 8 = 1 9 XOR 2 = 11 9 XOR 4 = 13 9 XOR 1 = 8 Maximum = 13.
ในการแก้ปัญหานี้ วิธีง่ายๆ และไร้เดียงสาคือการคำนวณชุดค่าผสมทั้งหมดและพิมพ์ XOR สูงสุดตามที่แสดงในตัวอย่างด้านบน
แต่สิ่งนี้จะไม่เป็นผลเนื่องจากโค้ดอาศัยสองลูปซึ่งทำให้ความซับซ้อนของคำสั่ง O(n^2)
เราจะเห็นวิธีแก้ปัญหาที่ดีกว่านี้
มันคือการใช้โครงสร้างข้อมูลแบบทดลองซึ่งจะเก็บไบนารีขององค์ประกอบทั้งหมดของอาร์เรย์ B สำหรับการจับคู่กับอาร์เรย์ A เพื่อค้นหา XOR สูงสุด
ดังนั้นสำหรับองค์ประกอบของอาร์เรย์ A เราจะตรวจสอบบิตที่สำคัญที่สุดและพยายามทำให้เป็น 1 และไปที่ MSB ถัดไป ต่อไปนี้เราจะได้องค์ประกอบ XOR สูงสุดสำหรับองค์ประกอบของ A ในอาร์เรย์ B
ตัวอย่าง
โปรแกรมค้นหา XOR สูงสุดของทุกองค์ประกอบในอาร์เรย์ด้วยอาร์เรย์อื่น
#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
