C++でXORをゼロとしてサブ配列の数を最大化します

整数値を含む配列Arr[]が与えられます。目標は、XORが0のサブアレイの最大数を見つけることです。サブアレイのビットは、何度でも交換できます。

注：-1 <=Arr [i] <=10 ¹⁸

ビットを交換してサブアレイのXORを0にするには、次の2つの条件が満たされている必要があります。-

• 左から右の範囲のセットビット数が偶数の場合。

• 任意の範囲のビットの合計<=2（セットビットの最大数）

このためのさまざまな入出力シナリオを見てみましょう-

で −arr [] ={1,2,5,4}

アウト −

1番目の条件のみを満たすサブアレイ：4

両方の条件を満たすサブアレイ：3

で − arr [] ={3,7,2,9}

アウト −

1番目の条件のみを満たすサブアレイ：6

両方の条件を満たすサブアレイ：3

以下のプログラムで使用されるアプローチは次のとおりです-

このアプローチでは、ビットを交換してサブアレイのXORを0にするために、2つの条件が満たされる必要があることを確認しました。-左から右の範囲のセットビット数が偶数の場合、または任意の範囲のビットの合計<=2（セットビットの最大数）

• 入力配列Arr[]を取得し、その長さを計算します。

• 関数removeSubarr（int arr []、int len）は、条件2を満たさないサブ配列の数を返します。

• 初期カウントを0とします。

• forループを使用して配列を反復し、変数sumとmaxValを取得します。

• 別のforループを使用して、60個のサブ配列の範囲で反復します。60を超えると、条件2がfalseになることはありません。

• 合計する要素を追加し、maxValで最大にします。

• 合計が偶数で2*maxVal>合計の場合、条件2が満たされないためカウントをインクリメントします。

• 両方のループの終わりにカウントを返します。

• 関数findSubarrays（int arr1 []、int len1）は、入力配列とその長さを受け取り、上記の両方の条件を満たすサブ配列の数を返します。

• プレフィックス配列を使用して、条件1のみに続くサブ配列の数を計算します。

• forループを使用して配列をトラバースし、各要素に設定されたビット数である__builtin_popcountll（arr1 [i]）を設定します。

• forループを使用してプレフィックス配列にデータを入力し、prefix [i] =prefix [i] + prefix [i-1]を設定します。ここで、最初の要素を除きます。

• プレフィックス配列の奇数値と偶数値をカウントします。

• tmp1 =（oddcount *（oddcount-1））/2およびtmp2=（evencount *（evencount-1））/ 2を設定し、両方の合計として結果を求めます。

• 結果は、条件1のみを満たすサブ配列の合計になります。

• 結果を印刷します。

• 次に、結果をresult =result --removeSubarr（arr1、len1）で更新します。

• これで、結果には両方の条件を満たすサブ配列が含まれます。

• 結果をもう一度印刷します。

例

#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int removeSubarr(int arr[], int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      int sum = 0;
      int maxVal = 0;

      for (int j = i; j < min(len, i + 60); j++){
         sum = sum + arr[j];
         maxVal = arr[j] > maxVal ? arr[j]: maxVal;

         if (sum % 2 == 0){
            if( 2 * maxVal > sum)
               { count++; }
         }
      }
   }
   return count;
}
int findSubarrays(int arr1[], int len1){
   int prefix[len1];
   int oddcount, evencount;
   int result;
   for (int i = 0; i < len1; i++)
   { arr1[i] = __builtin_popcountll(arr1[i]); }

   for (int i = 0; i < len1; i++){
      prefix[i] = arr1[i];
      if (i != 0)
         { prefix[i] = prefix[i] + prefix[i - 1]; }
      }
      oddcount = evencount = 0;
      for (int i = 0; i < len1; i++){
         if (prefix[i] % 2 == 0)
            { evencount = evencount +1; }
         else
            { oddcount = oddcount +1; }

      }
      evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

出力

上記のコードを実行すると、次のOutが生成されます

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3