이 문제에서는 각각 n개의 요소로 구성된 두 개의 배열 A와 B가 제공됩니다. 우리의 임무는 배열의 모든 요소와 다른 배열의 가능한 최대 XOR을 찾는 프로그램을 만드는 것입니다.
배열 B를 사용하여 배열 A의 각 요소에 대한 최대 XOR을 계산해야 합니다. 즉, 배열 A의 각 요소에 대해 배열 B에서 최대 XOR 값을 갖는 요소를 선택합니다.
문제를 이해하기 위해 예를 들어 보겠습니다. −
입력 -
array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1} 출력 -
11 14 15 13
설명 -
배열 A의 각 요소와 배열 B의 모든 요소의 XOR 조합을 보고 각각의 최대값을 선택합시다.
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) 순서의 복잡성을 만드는 두 개의 루프에 의존하기 때문에 이것은 효과적이지 않습니다.
따라서 문제에 대한 더 나은 솔루션을 보게 될 것입니다.
최대 XOR을 찾기 위해 배열 A와의 일치를 위해 배열 B의 모든 요소의 바이너리를 저장할 trie 데이터 구조를 사용하는 것입니다.
따라서 배열 A의 요소에 대해 최상위 비트를 확인하고 1로 만들려고 합니다. 그리고 다음 MSB로 이동합니다. 이에 따라 배열 B의 A 요소에 대한 최대 XOR 요소를 얻습니다.
예시
다른 배열이 있는 배열의 모든 요소에 대해 가능한 최대 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