XORING Ninja problem

#1

I am failing some test cases in this problem please suggest the change https://ide.codingblocks.com/s/359575

#2

Hey @coderajay03
please share link to the question.

#3

Sorry forgot that

#4

and please see this code not the previous one

#5

Hey @coderajay03
You are doing
int comb=(1<<n)-1;
but this is not possible because n can be 10^5

So u have to change ur approach.

Here is the editorial solution
Solution: Find the OR of all the elements and multiply it with 2^(n-1) where n is the total number of elements. This gives us the answer.

Idea:

There will be a total of subsets.
If bit of any element is set, then that bit will be set in the xor of half of the total subsets which is .
To find out all of the set bits in all of the numbers we find the OR of all of the numbers.
Since each set bit appears in half of the total subsets, we multiply the OR of all of the numbers with 2^n-1 to get the final result.

#6

what if I store comb in long long then also getting error and please tell where my approach is failing because half of the test cases are getting passed .

#7

bro 1<<10^5
is 2^(10^5) u cant store it in any variable

This is wrong with your approach

#8

I didnt understood the editorial solution

#9

Assume we have{1,2,3}
So the editorial says
Take or of all nos ,temp=1|2|3=3
Now it says if some bit is set in OR then it will be set in galf of total subsets
Lets check this fact by generating subsets
empty
1
2
3
1^2=3
1^3=2
2^3=1
1^2^3=0
Now first bit is set in (1,3,3,1)
Second bit is set in (2,3,3,2)
So the fact is checked

So the final answer is Or of array *2^n-1 == temp*2^(n-1)

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.