HackerEarth Bitwise AND sum problem solution

In this HackerEarth Bitwise AND sum problem solution You are given an array A consisting of N positive integers. Here, f(i,j) is defined as the bitwise AND of all elements of the array A after replacing all elements of A in the range [i,j] (both inclusive) with (2 to power 25 - 1). Your task is to find:

                              

-f(1,N) + sigma(i=1,N) sigma(j=1,N)f(i,j)                             

Note that after calculating the value f(i,j) for some (i,j), the array is restored back to its original form. Therefore, calculating f(i,j) for each (i,j) pair is independent. You are given T test cases.

HackerEarth Bitwise AND sum problem solution.

#include <bits/stdc++.h>
using namespace std;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> arr(n);
        int i;
        for(i = 0; i < n; i++)
            cin >> arr[i];
        long long ans = 0;
        for(int bit = 0; bit < 25 ; bit++){
            vector<int> vec;
            for(i = 0; i < n ; i++)
                vec.push_back((arr[i] >> bit)&1);
            int j = n;
            while(j > 0 && vec[j - 1] == 1)
                j--;
            // [j, n-1] has all ones
            j = max(j, 1);
            ans = ans + (n - j + 1)*1ll*(1 << bit);
            for(i = 1; i < n ; i++) // removing from 'i'
            {
                if(vec[i-1] == 0)
                    break;
                j = max(j, i + 1);
                ans = ans + (n - j + 1)*1ll*(1 << bit);
            }
        }
        ans = ans - (1ll << 25) + 1;
        cout << ans << '\n';
    }
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 5e5 + 14, B = 25;
int a[MAX_N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        ll ans = 0;
        for (int i = 0; i < B; ++i) {
            int l = 0;
            while (l < n && (a[l] >> i & 1))
                ++l;
            int r = n;
            while (r > l && (a[r - 1] >> i & 1))
                --r;
            ans += (l == n ? n * ll(n + 1) / 2 - 1 : (l + 1) * ll(n - r + 1) - 1) * (1 << i);
        }
        cout << ans << '\n';
    }
}