HuTao_Oya_OyaOya's blog

By HuTao_Oya_OyaOya, history, 5 months ago, In English

Problem Link

Problem in short : Find sum of XOR of all subarrays of size>1 in the given array of size n in linear time.

My idea is to get the prefix sum array of XORs and now the problem is reduced to finding XOR between all possible pairs in prefix XOR array.

I tried for hours to debug the code but couldn't figure out what did I do wrong. Any help would be greatly appreciated.

Old Code

UPD :

AC
What was the problem earlier ?

Thanks srinivas1999 xQConqueror vaibhav2740

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your approach is right but code is wrong.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't you use segment tree to solve it in O(nlogn) ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Solution

Code from, i just subtract the sum of all subarrays of 1 element

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

no thanks to me ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just solved it :3 very cute problem! the idea is to prefix sum on the bits of the number themselves, then we just count the number of subarrays on the bits such as the number of 1's is odd without the number it self, can be done in O(n) per bit so O(nlogn), again very cute and unexpected/smart solution from my side :D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

To find XOR between every pair you can sum the contribution for each bit individually.

First We will make a array cnt[i] = #Number of elements with i-th bit on(equal to one).

For i-th bit we add $$$2^{i} * cnt[i] * (n - cnt[i])$$$ because i-bit will be on when there is exactly one number have that bit on.