OR of Pairwise XOR (BITS manipulation)

Hey there!!

A new one again on BITs manipulation

It is a question given here :- click here.

We encourage you to try solving problem first by yourself but still if you are getting trouble then move on to tutorials.

So, in this question we require to find OR of (XOR of all pairs) that can be made in a set.

As you can see time limit for this question is 2 sec. So, going by conventional method will require O(n^2) complexity solution. As n can be 10^6, Hence it is difficult to pass under given constraints.

So what should be the logic?




Since this question deals with bits manipulation so let us thinks that way.

We know a XOR operation returns 1  if any one of the bit is 1 but not both. So let us apply this knowledge here.

And OR operation returns 1 if all BITS are not 0.

EXAMPLE given is :

1 8 9 2 3      and its answer is       11.

Lets do it:
BITS Representation:

1: 0001           8:1000           9:1001         2:0010           3: 0011

A quick snapshot of ALGORITHM:

1. Pick up a position and traverse that position bit in all numbers one by one.
2. Count the numbers that have set bit(1) at that position.(suppose k)
3. Now we know that OR of all XOR pairs will return 0 if all XOR pair values give 0.
4. Here only two cases are possible either 0 or 1 after OR operation.
5. Proceed as follows.

WATCH 3rd Case more carefully.

So here going bit by bit for every no._________
Lets pick up first bit i.e. 0th bit.

• 0th bit are :  1,0,1,0,1

Here XOR of all pairs possible return mixture of 0's and 1's and then OR of all those pair should return 0 or 1. Now we see that OR give 0 if all bits are 0. It is known that in above case at least one pair exist which gives 1. Hence overall OR of all pairs returns 1.
Hence ans= ans + (2^0)*(1) = 1

• 1st bit are : 0,0,0,1,1

Similarly here XOR of all pairs possible return mixture of 0's and 1's and then OR of all those pair should return 0 or 1. Now we see that OR give 0 if all bits are 0. It is known that in above case at least one pair exist which gives 1. Hence overall OR of all pairs returns 1.
Hence ans= ans + (2^1)*(1) = 2

• 2nd bit are : 0,0,0,0

Here XOR of all possible pair returns 0. Lets say pairs return 0,0,0,0...... So now OR of  all possible pairs result is surely going to give 0 and OR operation returns 0 if all bits are zero.
Hence ans= ans + (2^2)*(0) = 0


Same will be the case when all bits are 1 ...... XOR returns 0 and OR of all pairs will then be 0 because all pairs returned 0.

• 3rd bit are : 0,1,1,0,0

Here like first case XOR of all pairs possible return mixture of 0's and 1's and then OR of  all those pair should return 0 or 1. Now we see that OR give 0 if all bits are 0. It is known that in above case at least one pair exist which gives 1. Hence overall OR of all pairs returns 1.
Hence ans= ans + (2^3)*(1) = 8


and here is our ans after adding all ans = 11.

• If you are wondering how to know that i-th bit is 1. Then here is the operation 1&(a[j]>>i) this will whether i-th bit is set or not.

Complexity of this ALGO is O(32*n).(assuming at most 32 bit number present) and this will pass in given constraints.

TIPS:

1. there can be 32 bits so to be safe loop till 32 bits.
2. use long long int.

Hope u enjoyed knowing about this problem.

TRYING is best learning, So try yourself first,Still facing problem you can contact for solution or comment below.