Max length of common interval whose Bitwise OR, AND are equal in both Arrays

#include <bits/stdc++.h>

using namespace std;

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)

            val += (1 << j);

    }

    return val;

}

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)

            val += (1 << j);

    }

    return val;

}

int largestLength(vector<int>& A, vector<int>& B)

{

    int N = A.size();

    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];

        }

    }

    int ans = 0;

    for (int i = 0; i < N; i++) {

        int low = 0, high = N - i;

        while (low < high) {

            int mid = (low + high + 1) / 2;

            if (orCalculate(i, mid, prefixBitSumA)

                <= andCalculate(i, mid, prefixBitSumB))

                low = mid;

            else

                high = mid - 1;

        }

        if (orCalculate(i, low, prefixBitSumA)

            == andCalculate(i, low, prefixBitSumB))

            ans = max(ans, low);

    }

    return ans;

}

int main()

{

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

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

    cout << largestLength(A, B);

    return 0;

}

#include <bits/stdc++.h>

using namespace std;

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)

            val += (1 << j);

    }

    return val;

}

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)

            val += (1 << j);

    }

    return val;

}

int largestLength(vector<int>& A, vector<int>& B)

{

    int N = A.size();

    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];

        }

    }

    int ans = 0;

    for (int i = 0; i < N; i++) {

        int low = 0, high = N - i;

        while (low < high) {

            int mid = (low + high + 1) / 2;

            if (orCalculate(i, mid, prefixBitSumA)

                <= andCalculate(i, mid, prefixBitSumB))

                low = mid;

            else

                high = mid - 1;

        }

        if (orCalculate(i, low, prefixBitSumA)

            == andCalculate(i, low, prefixBitSumB))

            ans = max(ans, low);

    }

    return ans;

}

int main()

{

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

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

    cout << largestLength(A, B);

    return 0;

}