Écrivez du code en C++ pour trouver le nombre de sous-tableaux avec des bits ou des valeurs supérieurs ou égaux à K

Dans cet article, nous expliquerons brièvement comment résoudre le nombre de sous-tableaux avec OR>=K au niveau du bit en C++. Nous avons donc un tableau arr[] et un entier K, et nous devons trouver le nombre de sous-tableaux dont le OU (OU au niveau du bit) est supérieur ou égal à K. Voici donc l'exemple du problème donné -

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

Façons de trouver la solution

Nous allons maintenant utiliser deux méthodes différentes pour résoudre le problème en utilisant C++ -

Force brute

Dans cette méthode, nous allons simplement Parcourez tous les sous-tableaux qui peuvent être formés et vérifiez si OR est supérieur ou égal à K. Si oui, nous ajouterons notre réponse.

Exemple

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

Output

4

Cette méthode est très simple mais elle a ses inconvénients car cette méthode n'est pas bonne pour des contraintes plus élevées et pour des contraintes plus élevées cela prend trop de temps car ceci La complexité temporelle de cette méthode est O( N *N), où N est la taille du tableau donné, nous allons donc maintenant adopter une méthode efficace.

Méthode efficace

Dans cette méthode, nous utiliserons certaines propriétés de l'opérateur OU, c'est-à-dire que même si nous ajoutons plus de nombres, il ne diminuera pas, donc si nous obtenons un sous-tableau de i à j, son OU est supérieur ou égal à K, alors chaque sous-tableau contenant la plage {i,j} aura un OU supérieur à K. Nous profitons de cette propriété et améliorons notre code.

Exemple

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

Output

4

Dans cette méthode, nous utilisons la recherche binaire et l'arbre de segments, ce qui permet de réduire la complexité temporelle de O(N*N) à O(Nlog(N)), c'est très bien . Désormais, contrairement à la procédure précédente, cette procédure peut également être appliquée à des contraintes plus importantes.

Conclusion

Dans cet article, nous avons résolu un problème pour trouver le nombre de sous-tableaux avec OR >= K en utilisant recherche binaire et arbres de segments avec une complexité temporelle O(nlog(n)). Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. 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!