COWA19A- Editorial

editorial
,
1

COWA19A

PROBLEM LINK:

Practice
Contest

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 (xN)(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.

1 Like