En C++, maximiser le nombre de sous-tableaux avec zéro XOR

Nous obtenons un tableau Arr[] contenant des valeurs entières. Le but est de trouver le nombre maximum de sous-tableaux dont le XOR est 0. Les bits de n'importe quel sous-tableau peuvent être échangés un nombre illimité de fois.

Remarque : - 118

Afin de rendre le XOR de n'importe quel sous-tableau à 0 en échangeant des bits, deux conditions doivent être remplies : -

• Si le nombre de bits définis est compris entre gauche et droite est un nombre pair.

• Pour la somme de bits dans une plage donnée

Examinons différents scénarios d'entrée et de sortie -

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

Out −

Sous-tableau qui ne satisfait qu'à la première condition : 4

Sous-tableau qui satisfait aux deux conditions : 3

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

Out −

Sous-tableau qui ne satisfait qu'à la première condition : 6

Sous-tableau qui satisfait les deux conditions : 3

La méthode utilisée dans le programme suivant est la suivante -

Dans cette méthode, nous observons que pour faire To XOR n'importe quel sous-tableau à 0 en échangeant les bits, deux conditions doivent être remplies : - Si le nombre de bits définis dans la plage de gauche à droite est pair ou pour une plage donnée, la somme des bits

• Obtenez le tableau d'entrée Arr[ ] et calculez sa longueur .

• La fonction removeSubarr(int arr[], int len) renvoie le nombre de sous-tableaux qui ne remplissent pas la condition 2.

• Réglez le décompte initial sur 0.

• Parcourez le tableau à l'aide d'une boucle for et prenez les variables sum et maxVal.

• Utilisez une autre boucle for pour parcourir la plage de 60 sous-tableaux, car au-delà de 60 sous-tableaux, la condition 2 ne sera jamais fausse.

• Ajoutez des éléments à additionner et prenez la valeur maximale dans maxVal.

• Si la somme est paire et 2 * maxVal > sum, incrémenter le décompte car la condition 2 n'est pas satisfaite.

• Les deux retours comptent à la fin des deux boucles.

• La fonction findSubarrays(int arr1[], int len1) accepte un tableau d'entrée et sa longueur, et renvoie le nombre de sous-tableaux qui remplissent les deux conditions ci-dessus.

• Prenez un tableau de préfixes pour compter le nombre de sous-tableaux qui ne satisfont que la condition 1.

• Utilisez une boucle for pour parcourir le tableau et définir chaque élément __builtin_popcountll(arr1[i]) C'est le nombre de bits définis.

• Utilisez une boucle for pour remplir le tableau de préfixes et définissez préfixe[i] = préfixe[i] + préfixe [i - 1] sauf pour le premier élément.

• Comptez les valeurs paires et impaires dans le tableau de préfixes.

• Définissez tmp1 = ( oddcount * (oddcount-1) )/2 et tmp2= ( Evencount * (evencount-1) )/2 et prenez le résultat comme la somme des deux.

• Le résultat sera la somme des sous-tableaux qui satisfont uniquement à la condition 1.

• Imprimez les résultats.

• Maintenant, mettez à jour le résultat avec result=result - removeSubarr( arr1, len1).

• Maintenant, le résultat contient des sous-tableaux qui satisfont aux deux conditions.

• Imprimez à nouveau les résultats.

Exemple

#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

Si nous exécutons le code ci-dessus, il générera la sortie suivante

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!