COWA19A

# PROBLEM LINK:

Time Complexity O(logn)

Given an integer N. We have to find the sum of bitwise-OR of all ordered pairs(a,b) {1<=a,b<=N}.

1=001

2=010

3=011

4=100

.

.

.

N

Make an array A[] of size 32. For (0<=i<=31) each ith bit compute the total no. of 1’s for all the elements from 1 to N. This can be computed in O(logn) time complexity.

```
while(n)
{
int k=log2(n);
k=pow(2,k);
n=n-k;
int i=0; // ith bit
int val=k/2;
// ex: if k=4, add val=4/2=2 to every ith bit having 2^i<4.
while(k>1)
{
a[i]+=val;
i++;
k=k/2;
}
a[i]+=n+1;
}
```

Now for all ordered pairs (a,b), if the ith index of A[] has x no. of 1’s then there are x no’s out of N having ith bit 1. So if we take Bitwise-OR of these x no’s with all the N no’s then the sum would be (x*N)*(2^i).

And for other (N-x) no’s the sum would be (N-x)(x)(2^i).

Now for each i compute the sum and add it up. This is the required answer.

for i 0 to 31

ans=(ans+(A[i]N)(2^i)+(N-x)(x)(2^i))

Don’t forget to take Modulo with 10^9+7.