In C++ geschriebener Code zum Abfragen der Anzahl von Array-Elementen in einem Bereich, in dem das K-te Bit gesetzt ist

In diesem Artikel diskutieren wir das Problem, die Anzahl der Elemente in einem bestimmten Bereich zu ermitteln, bei denen das k-te Bit wie −

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

gesetzt ist. Wir werden dieses Problem durch einen Brute-Force-Ansatz lösen und prüfen, ob dieser Ansatz funktioniert für höhere Einschränkungen. Wenn es nicht funktioniert, versuchen wir, uns eine neue effiziente Methode auszudenken.

Brute-Force-Methode

Bei dieser Methode durchlaufen wir einfach den Bereich und prüfen, ob das k-te Bit jedes Elements gesetzt ist, und wenn ja, erhöhen wir die Anzahl.

Beispiel

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

Ausgabe

0
1

Die zeitliche Komplexität der obigen Methode beträgt O(N*Q), wobei N die Größe des Arrays und Q die angegebene Anzahl von Abfragen ist besser für höher Die Einschränkungen gelten nicht, da dies zu viel Zeit in Anspruch nehmen würde. Daher werden wir jetzt versuchen, ein effizientes Programm zu erstellen.

Effiziente Methode

Bei dieser Methode verwalten wir ein 2D-Präfix-Summen-Array, das die Anzahl der für jede Indexposition verwendeten Bits enthält, und wir können es in einer O(1)-Komplexitätsantwort berechnen.

Beispiel

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

Ausgabe

2
3

Da wir ein Präfixarray verwalten, das uns hilft, die Antwort in der Zeitkomplexität O(1) zu finden, wird unsere Zeitkomplexität stark auf O(N) reduziert, wobei N die gegebene Größe ist des Arrays.

Erklärung des obigen Codes

In diesem Programm verwalten wir einen Präfixzähler für jeden Index des Arrays, der jede Anzahl von Bits zählt, die vor diesem Index verwendet werden. Jetzt haben wir die Präfixanzahl für jede Ziffer gespeichert, also müssen wir für die k-te Anzahl das k-te Präfix am L-1-Index von der k-ten Präfixanzahl am R-ten Index subtrahieren. das ist unsere Antwort.

Fazit

In diesem Artikel haben wir uns mit dem Problem befasst, eine Abfrage für einen Bereich von Array-Elementen mit gesetztem K-ten Bit zu lösen. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz (sowohl trivial als auch effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonIn C++ geschriebener Code zum Abfragen der Anzahl von Array-Elementen in einem Bereich, in dem das K-te Bit gesetzt ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!