Schreiben Sie Code mit C++, um die Anzahl der Subarrays mit Bits oder Werten größer oder gleich K zu ermitteln

In diesem Artikel erklären wir kurz, wie man in C++ nach der Anzahl der Subarrays mit bitweisem OR>=K auflöst. Wir haben also ein Array arr[] und eine Ganzzahl K und müssen die Anzahl der Unterarrays ermitteln, deren OR (bitweises OR) größer oder gleich K ist. Hier ist also das Beispiel des gegebenen Problems –

Input: arr[] = {1, 2, 3} K = 3
Output: 4

Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2

Möglichkeiten, die Lösung zu finden

Jetzt werden wir zwei verschiedene Methoden verwenden, um das Problem mit C++ zu lösen –

Brute Force

Bei dieser Methode gehen wir einfach vor Durchlaufen Sie alle Subarrays, die gebildet werden können, und prüfen Sie, ob OR größer oder gleich K ist. Wenn ja, werden wir unsere Antwort hinzufügen.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(int); // the size of our array.
    int answer = 0; // the counter variable.
    for(int i = 0; i < size; i++){
        int bitwise = 0; // the variable that we compare to k.
        for(int j = i; j < size; j++){ // all the subarrays starting from i.
            bitwise = bitwise | arr[j];
            if(bitwise >= k) // if bitwise >= k increment answer.
               answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

Ausgabe

4

Diese Methode ist sehr einfach, hat aber ihre Nachteile, da diese Methode für höhere Einschränkungen nicht geeignet ist und für höhere Einschränkungen zu viel Zeit in Anspruch nimmt, da dies der Fall ist. Die zeitliche Komplexität dieser Methode beträgt O( N *N), wobei N die Größe des gegebenen Arrays ist, also werden wir jetzt eine effiziente Methode verwenden.

Effiziente Methode

In dieser Methode verwenden wir einige Eigenschaften des OR-Operators, d. h. selbst wenn wir mehr Zahlen hinzufügen, wird er nicht kleiner. Wenn wir also ein Unterarray von i bis j erhalten, ist dessen OR größer oder gleich K Jedes Subarray, das den Bereich {i,j} enthält, hat ein ODER größer als K. Wir machen uns diese Eigenschaft zunutze und verbessern unseren Code.

Beispiel

#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // segment tree building
    if(start == end){
       t[v] = a[start];
       return;
    }
    int mid = (start + end)/2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays.
    if (l > r)
       return 0;
    if(tl == l && tr == r)
       return t[v];
    int tm = (tl + tr)/2;
    int q1 = query(2*v, tl, tm, l, min(tm, r));
    int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
    return q1 | q2;
}
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
    int answer = 0; // the counter variable.
    build(arr, 1, 0, size - 1); // building segment tree.
    for(int i = 0; i < size; i++){
        int start = i, end = size-1;
        int ind = INT_MAX;
        while(start <= end){ // binary search
            int mid = (start + end) / 2;
            if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
               ind = min(mid, ind);
               end = mid - 1;
            }
            else
               start = mid + 1;
        }
        if(ind != INT_MAX) // if ind is changed then increment the answer.
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}

Ausgabe

4

In dieser Methode verwenden wir eine binäre Suche und einen Segmentbaum, was dazu beiträgt, die Zeitkomplexität von O(N*N) auf O(Nlog(N)) zu reduzieren, das ist sehr gut . Im Gegensatz zum vorherigen Verfahren kann dieses Verfahren nun auch auf größere Randbedingungen angewendet werden.

Fazit

In diesem Artikel haben wir ein Problem gelöst, um die Anzahl von Subarrays mit OR >= K mithilfe der binären Suche und Segmentbäumen mit der Zeitkomplexität O(nlog(n)) zu ermitteln. 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. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonSchreiben Sie Code mit C++, um die Anzahl der Subarrays mit Bits oder Werten größer oder gleich K zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!