Dalam C++, maksimumkan bilangan subarray dengan sifar XOR

Kami mendapat array Arr[] yang mengandungi nilai integer. Matlamatnya adalah untuk mencari bilangan maksimum subarray yang XORnya ialah 0. Bit mana-mana subarray boleh ditukar beberapa kali.

Nota: - 118

Untuk menjadikan XOR mana-mana subarray kepada 0 dengan menukar bit, dua syarat mesti dipenuhi: -

• Jika bilangan set bit dalam julat dari kiri ke kanan ialah nombor genap.

• Untuk jumlah bit dalam mana-mana julat tertentu

Mari lihat pelbagai senario input dan output -

In −Arr[] = { 1,2,5,4 }

−Subarray yang hanya memenuhi syarat pertama: 4

Subarray yang memenuhi kedua-dua syarat: 3

In

− Arr[] = { 3,7,2,9 }

itu hanya memenuhi syarat syarat pertama: 6

Subarray yang memenuhi kedua-dua syarat: 3

Kaedah yang digunakan dalam atur cara berikut adalah seperti berikut -

Dalam kaedah ini, kami perhatikan bahawa untuk membuat To XOR sebarang sub-array kepada 0 dengan menukar bit, dua syarat mesti dipenuhi:- Jika bilangan bit set dalam julat dari kiri ke kanan adalah genap atau untuk mana-mana julat tertentu jumlah bit

• Dapatkan tatasusunan input Arr[ ] dan hitung panjangnya .

• Fungsi removeSubarr(int arr[], int len) mengembalikan bilangan subarray yang tidak memenuhi syarat 2.

• Tetapkan kiraan awal kepada 0.

• Lelaran ke atas tatasusunan menggunakan gelung for dan ambil jumlah pembolehubah dan maxVal.

• Gunakan gelung for yang lain untuk mengulang dalam julat 60 sub-tatasusunan, kerana melebihi 60 sub-tatasusunan, syarat 2 tidak akan pernah palsu.

• Tambah elemen untuk dijumlahkan dan ambil nilai maksimum dalam maxVal.

• Jika jumlah genap dan 2 * maxVal > jumlah, menambah kiraan sebagai syarat 2 tidak berpuas hati.

• Kedua-dua gelung kembali dikira pada penghujung.

• Fungsi findSubarrays(int arr1[], int len1) menerima tatasusunan input dan panjangnya, dan mengembalikan bilangan subarray yang memenuhi dua syarat di atas.

• Ambil tatasusunan awalan untuk mengira bilangan subtatasusunan yang hanya memenuhi syarat 1.

• Gunakan gelung for untuk lelaran melalui tatasusunan dan tetapkan setiap elemen __builtin_popcountll(arr1[i]) Ini ialah bilangan bit yang ditetapkan di dalamnya.

• Gunakan gelung for untuk mengisi tatasusunan awalan dan tetapkan awalan[i] = awalan[i] + awalan [i - 1] kecuali elemen pertama.

• Kira nilai ganjil dan genap dalam tatasusunan awalan.

• Tetapkan tmp1 = ( oddcount * (oddcount-1) )/2 dan tmp2= ( Evencount * (evencount-1) )/2 dan ambil hasilnya sebagai jumlah kedua-duanya.

• Hasilnya ialah jumlah subarray yang hanya memenuhi syarat 1.

• Cetak hasilnya.

• Sekarang kemas kini keputusan dengan result=result - removeSubarr( arr1, len1).

• Kini hasilnya mengandungi subarray yang memenuhi kedua-dua syarat.

• Cetak hasilnya semula.

Contoh

#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;
}

Output

Jika kita menjalankan kod di atas, ia akan menghasilkan output berikut

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

Atas ialah kandungan terperinci Dalam C++, maksimumkan bilangan subarray dengan sifar XOR. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!