 Barclyas HackerEarth Challenge

You are given an integer N You need to calculate the Bitwise-OR sum of all ordered pairs (i,j):(1≤i,j≤N) . Print the value of sum modulo 10^9+7 (the remainder when sum is divided by 10^9+7

Example Case:
Input: 2
Output :(1|1 + 1|2 + 2|1 + 2|2 ) modulo (10^9+7) = 9.

Could Someone Suggest an efficient approach

using namespace std;
const unsigned long long int MOD = 1000000007;

unsigned long long int pairAndSum(vector &vect, unsigned long long int n)
{
unsigned long long int ans = 0;
for (unsigned long long int i = 0; i < 32; i++)
{
unsigned long long int k = 0;
for (unsigned long long int j = 0; j < n; j++)
if ( !(vect[j] & (1 << i)) )
k++;
ans +=(((1<<i)%MOD) ((n(n-1)/2)%MOD - (k*(k-1)/2)%MOD))%MOD;
}
return ans;
}
int main()
{
unsigned long long int n,i; cin>>n;
unsigned long long int arr[n];
vector vec(n);
for(i=0;i<n;i++)
vec[i]=i+1;

cout << (((2%MOD)*(pairAndSum(vec, n)%MOD))+(n*(n+1)/2)%MOD)%MOD << endl;
return 0;


}

This could fetch a partial of 60/100 points , Other test cases gave WA

The Challenge is now over

1 Like

When did the challenge ended?
I think someone asked in the midst of the contest. Anyways you can have a look at the soln here

1 Like

I will tell you what I did . I basically calculated for each bit , in how many numbers the bit is set and in how many numbers bit is unset

for ex ,for each bit
x = number of numbers in which bit is set
y = number of number in which bit is not set

then that bit will be set in following pairs ( OR of this numbers )

1. Each of x numbers when taken in OR with (1…n) = xn bits
2.Each of y numbers taken in OR with x numbers = x
y bits

In this way perform bit addition from LSB to MSB

For reference my code

3 Likes

hey @ashforever007 can you please explain your approach more clearly by some sort of an example thanks and please do share the solution for problem 2 “count all” if possible.

ll ans = n*(n+1)/2%M;

ll dp;
memset(dp, 0, sizeof(dp));
for (ll i = 1; i <= n; i++)
{
ll ci=i;
for (ll j = 0; j < 32; j++) {

  if (ci&1)
{
ans += 2 * (1 << j) * (i - 1);
dp[j] += 1;
}
else

{
ans += 2 * (1 << j) * dp[j];
}
ci>>=1;
ans%=M;
}


}

3 Likes

Yes i realized someone asked it when the challenge was live. Such practices are unfair to other participants , anyways thank you for the link.

1 Like

Use the concept of divisor sieve.

Divisor Sieve

1 Like

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.

https://www.codechef.com/problems/AND
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 ? @ssrivastava990 try your best bro and do let us know that your approach worked or not.

@gagangaur @karangreat234 @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 | arr + arr | arr +

// ... 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);

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