CODEWITHSUNDEEP
arraysbit-manipulationxor
Akshay Bhasin
Akshay Bhasin

Reputation: 611

Sum of xor of all subsequences in an array

I have an array of length say N(upto 10^5) and each element in it can be upto 10^9. Now i want know if there's some techniques or fast algorithm through which I can find sum of xor of all subsequences of the array. For example,
if N is 3
The elements are 1, 2, 3.
So the subsequences will be {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} and xor sum of all these equals to 12.
Pls help...

Upvotes: 1

Views: 4249

Answers (1)

JVJ
JVJ

Reputation: 109

Since your example basically shows xor sum of al subsets. Why dont you see this : https://math.stackexchange.com/questions/712487/finding-xor-of-all-subsets

Upvotes: 1

Related Questions