Longueur maximale de l'intervalle commun dont OU au niveau du bit, ET sont égaux dans les deux tableaux

Longueur maximale de l’intervalle commun dont OU au niveau du bit, ET sont égaux dans les deux tableaux

Étant donné deux tableaux UN et B de longueur Ntrouver la longueur maximale d’un intervalle commun de A et B tel que le OU au niveau du bit des éléments dans l’intervalle de A est égal à le ET au niveau du bit des éléments dans l’intervalle de B.

Formellement, étant donné les indices i et j (0 ≤ i ≤ j < N), trouver la valeur maximale de j-i+1 tel que: (UN[i] OU UN[i+1] OU … OU UN[j]) = (B[i] ET B[i+1] ET … ET B[j])

Exemples:

Saisir: UN[] = {2, 1, 3, 3}, B[] = {15, 3, 7, 11}
Sortir: 4
Explication: OU(2, 1) = ET(15, 3), Longueur = 2,
OU(2, 1, 3, ) = ET(15, 3, 7), Longueur = 3,
OU(2, 1, 3, 3) = ET(15, 3, 7, 11), Longueur = 4,
OU(1, 3) = ET(3, 7), Longueur = 2,
OU(1, 3, 3) = ET(3, 7, 11), Longueur = 3, etc. La plus grande longueur est donc 4.

Saisir: UN[] = {1, 2, 3, 4}, B[] = {4, 3, 7, 11}
Sortir: 2
Explication: OU(2, 3) = ET(3, 7), Longueur = 2, La plus grande longueur de sous-tableau est 2.

Approche: Le problème donné peut être résolu sur la base de l’observation suivante suivie de la recherche binaire :

Bitwise AND diminuera ou restera le même en prenant continuellement AND avec des éléments.

Alors que Bitwise OR augmentera ou restera le même en prenant continuellement OR avec des éléments.

Ces propriétés ci-dessus créeront une monotonie afin que nous puissions utiliser la recherche binaire pour calculer la plus grande longueur.

Suivez les étapes ci-dessous pour résoudre le problème :

Créez un tableau de somme de préfixes 2D pour chaque bit des deux tableaux. Avec ce pré-calcul, nous pouvons calculer OU et ET au niveau du bit en temps presque constant.
Ensuite, pour chaque index, nous utilisons la recherche binaire où low est égal à zéro et high sera la longueur de l’index i au dernier index.
- Si OR de longueur mid commençant par l’indice i est inférieur ou égal à AND de longueur mid, alors low est réglé sur mid sinon high est réglé sur mid-1.
Après avoir calculé la plus grande longueur à chaque index avec la condition ci-dessus en utilisant la recherche binaire, nous prenons maximum avec répond qui sera notre réponse.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

C++

// C++ implementation to find the largest length sub-array
// of two arrays A and B such that bitwise-OR of A from
// index i to j and bitwise-AND of array B from index i to j
// are equal
#include <bits/stdc++.h>
using namespace std;

// function for calculating bitwise OR of length 'length'
// from index i
int orCalculate(int st, int length,
                vector<vector<int> >& bitPrefix)
{
    int val = 0;
    for (int j = 0; j < 32; j++) {
        int cnt
            = bitPrefix[st + length][j] - bitPrefix[st][j];
        if (cnt != 0)

            // If atleast one jth bit is set
            // between that range, it will
            // be added to val
            val += (1 << j);
    }
    return val;
}

// Function for calculating bitwise AND
// of length 'length' from index i
int andCalculate(int st, int length,
                 vector<vector<int> >& bitPrefix)
{
    int val = 0;
    for (int j = 0; j < 32; j++) {
        int cnt
            = bitPrefix[st + length][j] - bitPrefix[st][j];
        if (cnt == length)

            // if jth bit is set in all
            // elements of that range, it
            // will be added to val
            val += (1 << j);
    }
    return val;
}

// Function for calculating largest length
// sub-array of two arrays A and B such
// that bitwise-OR of A from index i to j
// and bitwise-AND of array B from index
// i to j are equal
int largestLength(vector<int>& A, vector<int>& B)
{
    int N = A.size();

    // Creating 2D vectors for prefix
    // bit's sum for both arrays
    vector<vector<int> > prefixBitSumA(N + 1,
                                       vector<int>(32, 0)),
        prefixBitSumB(N + 1, vector<int>(32, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 32; j++) {
            prefixBitSumA[i + 1][j]
                = ((A[i] & 1 << j) ? 1 : 0)
                  + prefixBitSumA[i][j];
            prefixBitSumB[i + 1][j]
                = ((B[i] & 1 << j) ? 1 : 0)
                  + prefixBitSumB[i][j];
        }
    }

    // Initializing ans variable
    // for storing answer
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int low = 0, high = N - i;

        // Binary search while loop
        while (low < high) {
            int mid = (low + high + 1) / 2;
            if (orCalculate(i, mid, prefixBitSumA)
                <= andCalculate(i, mid, prefixBitSumB))
                low = mid;

            // Condition mentioned above
            else
                high = mid - 1;
        }

        // If final result for this index
        // 'low' also satisfying problem's
        // condition then take max with 'ans'
        // otherwise 'low' is not
        // considered as result
        if (orCalculate(i, low, prefixBitSumA)
            == andCalculate(i, low, prefixBitSumB))
            ans = max(ans, low);
    }

    // Final answer
    return ans;
}

// Driver code
int main()
{

    vector<int> A = { 2, 1, 3, 3 };

    vector<int> B = { 15, 3, 7, 11 };

    // Function Call
    cout << largestLength(A, B);

    return 0;
}

Complexité temporelle : O(N*logN), où N est la longueur du tableau (logN pour une recherche binaire pour chaque index),
Espace Auxiliaire : O(N), O(N*32*2) pour un préfixe BitArray 2D égal à O(N).