Fragen Sie die bitweise ODER-Verknüpfung eines bestimmten Arrays innerhalb des Indexbereichs mit C++ ab

In diesem Artikel erhalten wir eine Reihe von Ganzzahlen. Unsere Aufgabe besteht darin, das bitweise ODER aller Zahlen in einem bestimmten Bereich zu finden, zum Beispiel

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7

Bei dem gegebenen Problem werden wir es mit einem Brute-Force-Ansatz lösen und dann prüfen, ob es auf höhere Einschränkungen angewendet werden kann. Wenn nicht, optimieren wir unsere Methode, um den höheren Einschränkungen gerecht zu werden.

Brute-Force-Methode

Bei dieser Methode durchlaufen wir einfach jeden Bereich, zählen bitweise oder alle Zahlen in diesem Bereich und drucken unsere Antwort aus.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // size of our array
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for(int i = 0; i < q; i++) { // traversing through all the queries
      long ans = 0;
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
         ans |= arr[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

Ausgabe

7
3

Die zeitliche Komplexität dieses Ansatzes beträgt O(N*Q), wobei N die Größe des Arrays und Q die Anzahl der Abfragen ist. Wie Sie sehen, gilt diese Komplexität nicht für höhere Einschränkungen, daher optimieren wir nun unsere Methode so, dass sie auch für höhere Einschränkungen funktioniert.

Effiziente Methode

Bei dieser Methode zählen wir die Anzahl der Präfixziffern und prüfen dann, ob die Zahl einen bestimmten Satz von Bits hat. Wenn ja, dann nehmen wir diesen Punkt in die Antwort auf; andernfalls behalten wir diesen Punkt bei.

Beispiel

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
   for (int j = 31; j >= 0; j--) {
      prefixbits[j][0] = ((arr[0] >> j) & 1);
      for (int i = 1; i < n; i++) {
         prefixbits[j][i] = arr[i] & (1LL << j);
         prefixbits[j][i] += prefixbits[j][i - 1];
      }
   }
   return;
}
int check(int l, int r) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as long
   for (int i = 0; i < 32; i++) {
      int x;
      if (l == 0)
         x = prefixbits[i][r];
      else
         x = prefixbits[i][r] - prefixbits[i][l - 1];
      if (x != 0)
         ans = (ans | (1LL << i));
   }
   return ans;
}
int main() {
   int arr[] = {7, 5, 3, 5, 2, 3};
   int n = sizeof(arr) / sizeof(int); // size of our array
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for (int i = 0; i < q; i++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

Ausgabe

7
3

Die zeitliche Komplexität dieser Methode beträgt O(N), wobei N die Größe des Arrays ist, sodass diese Methode an höhere Einschränkungen angepasst werden kann.

Erklärung des obigen Codes

Bei dieser Methode zählen wir die Anzahl der Präfixziffern und speichern sie. Jetzt berechnen wir eine Abfrage, bei der wir über diese Präfixanzahl iterieren und die Bitanzahl von l-1 entfernen, sodass wir die Bitanzahl einer Zahl im Bereich [l, r] haben, da wir wissen, ob in einer beliebigen Zahl ein Bit gesetzt ist Wenn Sie es also bitweise mit einer anderen Zahl verknüpfen, bleibt das Bit gesetzt. Mit dieser Eigenschaft von bitweisem ODER prüfen wir, ob die Bitanzahl nicht Null ist, was bedeutet, dass sich eine Zahl im Bereich mit dem gesetzten Bit befindet, also setzen wir das Antwortbit und setzt die Schleife fort, um schließlich die Antwort auszugeben.

Fazit

Dieser Artikel löst das Problem der Berechnung einer bitweisen ODER-Abfrage im Indexbereich [L, R] bei gegebenem Array. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonFragen Sie die bitweise ODER-Verknüpfung eines bestimmten Arrays innerhalb des Indexbereichs mit C++ ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!