Code écrit en C++ pour interroger le nombre d'éléments de tableau dans une plage dont le Kème bit est défini

Dans cet article, nous discuterons du problème de trouver le nombre d'éléments dans une plage donnée qui ont un k-ième bit défini comme −

Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
   0
   1

Nous allons résoudre ce problème par une approche par force brute et voir si cette approche fonctionne pour des contraintes plus élevées. Si cela ne fonctionne pas, nous essayons de penser à une nouvelle méthode efficace.

Méthode Brute Force

Dans cette méthode, nous parcourons simplement la plage et vérifions si le kème bit de chaque élément est défini et si c'est le cas, nous incrémentons le nombre.

Exemple

#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
   if (n & (1 << (k - 1)))
   return true;
   return false;
}
int query(int L, int R, int K, int arr[]) {
   int count = 0; // counter to keep count of number present in the range
   for (int i = L; i <= R; i++) { // traversing the range
      if (Kset(arr[i], K)) {
         count++;
      }
   }
   return count;
}
int main() {
   int arr[] = { 4, 5, 7, 2 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int queries[][3] = { // given L, R and k
      { 2, 4, 4 },
      { 3, 5, 1 }
   };
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries

   for (int i = 0; i < q; i++) {
      int L = queries[i][0] - 1;
      int R = queries[i][1] - 1;
      int K = queries[i][2];

      cout << query(L, R, K, arr) << "\n";
   }
   return 0;
}

Sortie

0
1

La complexité temporelle de la méthode ci-dessus est O(N*Q), où N est la taille du tableau et Q est le nombre de requêtes donné, comme vous pouvez le voir, cette méthode est ; mieux pour plus haut Les contraintes ne s'appliquent pas car cela prendra trop de temps, donc maintenant nous allons essayer de faire un programme efficace.

Méthode efficace

Dans cette méthode, nous conserverons un tableau de somme de préfixes 2D qui contiendra le nombre de bits utilisés pour chaque position d'index et nous pourrons le calculer en réponse de complexité O (1).

Exemple

#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits

int P[100000][bits+1];

bool Kset(int n, int k) {
   if (n & (1 << (k - 1)))
      return true;
   return false;
}
void prefixArray(int n, int arr[]) { // building the prefix array
   for (int i = 0; i <= bits; i++) {
      P[0][i] = 0; // setting every bits initial count = 0
   }
   for (int i = 0; i < n; i++) {
      for (int j = 1; j <= bits; j++) {
         bool flag = Kset(arr[i], j);
         if (i) // we add previous count to the latest count(0)
            P[i][j] = P[i - 1][j];
         if (flag) { // if jth bit is set so we increase the count
            P[i][j]++;
         }
      }
   }
}
int query(int L, int R, int K) {
   if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
      return P[R][K] - P[L - 1][K];
   else
      return P[R][K];
}
int main() {
   int arr[] = { 8, 9, 1, 3 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of given array
   int queries[][3] = {
      { 1, 3, 4 },
      { 2, 4, 1 }
   };
   prefixArray(n, arr); // calling the function to create prefix array
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries

   for (int i = 0; i < q; i++) {
      int L = queries[i][0] - 1;
      int R = queries[i][1] - 1;
      int K = queries[i][2];
      cout << query(L, R, K) << "\n";
   }
   return 0;
}

Sortie

2
3

Puisque nous maintenons un tableau de préfixes qui nous aide à trouver la réponse en complexité temporelle O(1), notre complexité temporelle est considérablement réduite à O(N), où N est la taille donnée. du tableau.

Explication du code ci-dessus

Dans ce programme, nous maintenons un compteur de préfixes pour chaque index du tableau, qui compte chaque nombre de bits utilisés avant cet index. Maintenant, nous avons stocké le nombre de préfixes pour chaque chiffre, donc pour le k-ème nombre, nous devons soustraire le k-ème préfixe à l'index L-1 du k-ème nombre de préfixes au R-ème nombre d'index, c'est notre réponse.

Conclusion

Dans cet article, nous avons abordé le problème de la résolution d'une requête pour une plage d'éléments de tableau avec le jeu de bits Kth. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre (à la fois triviale et efficace). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera utile.

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!