C++の別の配列との配列内のすべての要素の可能な最大XOR

この問題では、それぞれn個の要素の2つの配列AとBが与えられます。私たちのタスクは、配列内のすべての要素と別の配列の可能な最大XORを見つけるプログラムを作成することです。

配列Aの各要素と配列Bの最大XORを計算する必要があります。つまり、配列Aの各要素について、最大XOR値を持つ配列Bの要素を選択します。

問題を理解するために例を見てみましょう-

入力 −

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を出力することです。

ただし、コードは2つのループに依存しているため、O（n ^ 2）の順序が複雑になるため、これは効果的ではありません。

そのため、問題に対するより良い解決策が見つかります。

最大のXORを見つけるために、配列Aとの一致のために配列Bのすべての要素のバイナリを格納するトライデータ構造を使用することです。

したがって、配列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