C++でサイズkのサブ配列の最大XOR値を見つける

この問題では、n個の要素と整数kで構成される配列arr[]が与えられます。私たちのタスクは、サイズkのサブ配列の最大XOR値を見つけることです。

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

入力

arr[] = {3, 1, 6, 2 ,7, 9} k = 3

出力

12

説明

すべてのサブ配列とサイズkのすべての要素のxor

{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12

ソリューションアプローチ

この問題の簡単な解決策は、2つのループを使用することです。 1つは配列を反復処理し、もう1つはサブ配列のすべての要素のXORを検索します。そして、すべての最大値を返します。

この解決策は問題ありませんが、問題を解決するためのより良いアプローチをとることができます。サイズkのサブ配列から開始して合計を見つける必要があります

次に、配列を繰り返し、XORに新しい要素を追加し、最初の要素を削除します。式x^a ^ x=aを使用して削除できます。

したがって、最初に実行する相互作用ごとに、XOR ^ arr [i --k]を実行します。これにより、最後のインデックス+1から現在のインデックス-1までのサブアレイの値が得られます。

次に、arr [i]を使用してサブアレイのXORを実行し、現在のXORを取得します。すべてのXORから最大値を見つけて返します。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
int findMaxSubArrayXOR(int arr[] , int n , int k) {
   int currentXORVal = 0 ;
   for (int i = 0 ; i < k ; i++)
   currentXORVal = currentXORVal ^ arr[i];
   int maxXor = currentXORVal;
   for (int i = k ; i < n; i++) {
      currentXORVal = currentXORVal ^ arr[i-k];
      currentXORVal = currentXORVal ^ arr[i];
      maxXor = max(maxXor, currentXORVal);
   }
   return maxXor;
}
int main() {
   int arr[] = {3, 1, 6, 2, 7, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 3;
   cout<<"The maximum XOR of subarray of size "<<k<<" is "<<findMaxSubArrayXOR(arr, n, k);
   return 0;
}

出力

The maximum XOR of subarray of size 3 is 12