Trong bài toán này, chúng ta có hai mảng A và B gồm n phần tử mỗi mảng. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm XOR tối đa có thể có của mọi phần tử trong một mảng với một mảng khác.
Chúng ta phải tính toán XOR tối đa cho mỗi phần tử của mảng A với mảng B, tức là đối với mỗi phần tử của mảng A, chúng ta sẽ chọn một phần tử trong mảng B sẽ có giá trị XOR lớn nhất.
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu vào -
array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1} Đầu ra -
11 14 15 13
Giải thích -
Hãy xem kết hợp XOR của từng phần tử của mảng A với tất cả các phần tử của mảng B và sau đó chọn giá trị tối đa cho mỗi phần tử.
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.
Để giải quyết vấn đề này, một cách tiếp cận đơn giản và dễ hiểu là tính toán tất cả các kết hợp và in ra XOR tối đa như trong ví dụ trên.
Nhưng điều này sẽ không hiệu quả vì mã dựa trên hai vòng lặp khiến độ phức tạp của nó theo thứ tự O (n ^ 2).
Vì vậy, chúng ta sẽ thấy một giải pháp tốt hơn cho vấn đề.
Nó là sử dụng cấu trúc dữ liệu trie sẽ lưu trữ nhị phân của tất cả các phần tử của mảng B cho trận đấu với mảng A, để tìm XOR tối đa.
Vì vậy, đối với một phần tử của mảng A, chúng tôi sẽ kiểm tra bit quan trọng nhất của nó và cố gắng biến nó thành 1. Và chuyển đến MSB tiếp theo. Sau đây, chúng ta sẽ nhận được phần tử XOR tối đa cho một phần tử của A trong mảng B.
Ví dụ
Chương trình tìm XOR tối đa có thể có của mọi phần tử trong một mảng với một mảng khác
#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;
} Đầu ra
The maximum possible XOR of every possible element in array A with Array B is 11 15 14 13