Use the concept of divisor sieve.
1 Like
and also if possible do share some resource for tackling the problems like hard sum of barclays if possible.
1 Like
Pure Brilliancy,Sir.
Check this editorial and problem on codechef.
They have very similar solutions :).
Seems like author just replaced AND with OR and removed i<j.
A brief summary is as follows.
Break the problem into a subproblem where given a binary array find sum of bitwise OR of it.
Once you solve that subproblem it won’t be hard for you to realize that answer is \sum_{i=0}^{31} ans(i)*2^i \mod m where m=10^9+7. (If constraints have 32 bits in number)
Hint for solving that subproblem :
Count number of “1” and number of “0”.
ans(i)= Count of OR_1 = total - count of OR_0 = (n*n) - (cnt_0*cnt_0) \mod m
1 Like
@gagangaur @avi this Divisor Sieve is very efficient and useful as this is also used in one another solution which is asked by rk_221b in this → Count all special element question (Help).
But how this divisor sieve is used here. I think instead of using divisor sieve e can use the concept of set bits as we know here a number is represented by 32 bits and the property of OR is to set the i’th bit , and count all the possible pairs , i will code and if works then definitely i will share 
Is this a sarcastic reply ?
Nope,I am new to bits-manipulation and this helped me a lot 
Thanks
understand the logic behind it then think how it can be modified for OR
1 Like
Any more similar problems you have ?
@gagangaur @anon55659401 @ganesh92 @avi141
Here u go–
// An efficient C++ program to compute sum of bitwise OR
// of all pairs
#include <bits/stdc++.h>
using namespace std;
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
int pairORSum( int arr[], int n)
{
int ans = 0; // Initialize result
// Traverse over all bits
for ( int i = 0; i < 32; i++)
{
// Count number of elements with i'th bit set
int k1 = 0; // Initialize the count
// Count number of elements with i’th bit not-set(ie., 0) `
int k0 = 0; // Initialize the count
for ( int j = 0; j < n; j++){
if ( (arr[j] & (1 << i)) )
`k1++;
else
k0++;
}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits, so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
ans = ans + (1<<i) * (k1*(k1-1)/2) +(1<<i)*(k1*k0) ;
ans %=MOD;
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = {1,2,3,4,5};
int n = sizeof (arr) / sizeof (arr[0]);
cout << pairORSum(arr, n) << endl;
return 0;
}
If any error in this programme or further explaination required then i will explain in best way
brilliant work bro @ssrivastava990 you have simplified the solution a lot to understand easily appreciated.
but i am still struggling with these three lines 
hope if you can simplify that too so that one can easily grasp this concept via some sort of an example if possible thanks. 
Seems incorrect… you did the same mistake I did in solution just above you…
There will be k1*k1 + 2*k1*k0 pairs
Or n*n - k0*k0
How??? Because when I calculate by using brute force and above algorithm all test case give same answers.
Is output of {1,2} in your code 9 ?? As given in this post itself ?
Single 2 means the array size is 1 only ??
Nope 2 meaning all elements from 1 to 2
Nope because my program take pairs a(I), a(j) where I<j
1 Like
I had posted the divisor sieve for the CountAll question.