Sum of bitwise OR of all possible subarrays of a given array

Question

I want to find the sum of bitwise OR of all possible subarrays of a given array.

This is what I did till now:

from operator import ior
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(1,n+1):
    for j in range(n+1-i):
        total += reduce(ior, a[j:j+i])
print(total)

But it is quite slow. How can I optimise it?

Answer 1

Since this question is from competition, I haven't answered till now.

Code:

#include <bits/stdc++.h>
using namespace std;
#define size 32
#define INT_SIZE 32
typedef long long int Int; 
typedef unsigned long long int Unt;
// Driver code
int main()
{
    Int n;
    cin>>n;
    Int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int zeros[size];
    for(int i=0;i<size;i++)
        zeros[i]=1;
    unsigned long long int sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<size;j++)
        {
            if(!(arr[i] & 1))
                zeros[j]++;
            else
            {
                sum+=(Unt)((Unt)zeros[j]*(Unt)(1<<j)*(Unt)(n-i));
                zeros[j]=1;
            }
            arr[i]>>=1;
        }
    }
    cout<<sum;
    return 0;
}

Logic:

Note*: This is my thinking process, this may not be understandable easily. Apology if I can't able to make you understand.

Take example : 5 (size of array) 1 2 3 4 5 (array)

for, 1 = 1.0

1,2 = 1.0 & 2.1

1,2,3 = 1.0 & 2.1 [3.0 & 3.1 won't be useful because they're already taken by 1 & 2]

1,2,3,4 = 1.0 & 2.1 & 4.2

1,2,3,4,5 = 1.0 & 2.1 & 4.2 are useful.

In above explanation, X.Y means Yth bit in number X is taken for OR operation.

For,

2 = 2.1

2,3 = 2.1 & 3.0 [Since 1.0 won't be available]

{continues..}

So, if you carefully observe although 3.0 is available, it's not being used while 1 is present.

If a bit needed to be used, same bit of previous numbers should be 0. [remember this, we'll use it later]

We'll create 1 array, named zeros, which gives count of last set bit of previous numbers at each position respectively [this sentence may give you confusion, try to read more, you may get clarity].

For given array,

At 1: 0 0 0

At 2: 1 1 0 {binary of 1 is 001}

At 3: 2 0 1 {binary of 2 is 010}

At 4: 3 0 0 {binary of 3 is 011}

At 5: 0 1 1 {binary of 4 is 100}

End: 0 2 0 {binary of 5 is 101}

What we did above is, if bit is set bit, we'll make it 0, else we add count so that we can understand how many numbers doesn't have set bit position wise respectively, means, before 3, 2 numbers doesn't have set bit at postion 2^2, 1 number doesn't have set bit at 2^0.

Now, we just need to multiply depending on their set bits.

If it is set bit, then we'll add (zeros[i]+1)(2^i)(n-i).

Answer 2

Let's first find the sum of bitwise OR of subarrays ending at position i. Let the OR of all the array elements from 1 to i is or and the ith element be a[i], the bits which are not set in a[i] but set in or are coming from some previous elements, let's take an example here,
1 2 2
at position 3, or = 3, a[i] = 2, or^a[i] = 1 this means 1 is coming from some previous element if we remove 1 OR of some subarray ending at i will be reduced. last position where bit 0 is on is 1. So the ans is,

ans = or*i

for all bits from 0 to m,
ans -= (i - lastposition[bit])*(1 << bit); //lastposition[] gives the last index at which bit is on.
Why last position? Beacuse the indexes before lastposition[], where this bit is on, will have no impact as the OR be reamin same due to the presence of this bit at lastposition[].

Final answer can be found out by summing up all the answers of 1 <= i <= n .

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
ll r, a, sum, pos[30];
int main()
{
   int n;
   cin >> n;
   rep(i,1,n)
  {
      cin >> a;
      r |= a;
      ll ex = r^a;
      ll ans = i*r;
      rep(bit,0,30)
        if(ex & (1 << bit))
            ans -= ((ll)(i - pos[bit])* ((ll)1 << bit));
     sum += ans;
     rep(bit,0,30)
        if(a & (1 << bit))
            pos[bit] = i;
}
   cout << sum << '\n';
}