HEIR_OF_SLYTHERIN's blog

Sum of XOR of all subarrays
By HEIR_OF_SLYTHERIN, history, 4 years ago, In English

Can someone explain the optimal solution for finding the sum of XOR of all sub-arrays of the array. Example:

Input : arr[] = {3, 8, 13} Output : 46

XOR of {3} = 3 XOR of {3, 8} = 11 XOR of {3, 8, 13} = 6 XOR of {8} = 8 XOR of {8, 13} = 5 XOR of {13} = 13

Sum = 3 + 11 + 6 + 8 + 5 + 13 = 46

Thanks in Advance.

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

Comments Comments (8)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It's a pretty standard problem you may get it here

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I didn't understand the O(N) solution can you please explain.

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Yeah, sure! Let's assume the array as bits and you want to find the no of subarrays having a particular bit (say ith bit) set.

      so let's assume the above example {3, 8, 13} as,

      • for 0th bit, {1, 0, 1}
      • for 1th bit, {1, 0, 0}
      • for 2nd bit, {0, 0, 1}
      • for 3rd bit, {0, 1, 1}

      so, now find no of subarrays with odd 1s for each of the bits.

      so how can we do this? see we can count no of subarrays starting with 0th index and have odd 1s then we can iterate over all $$$i$$$ letting it to be the starting index of the subarrays.

      so let say, for ith index have $$$x$$$ subarrays with odd 1s.

      if we encounter 1 at $$$ith$$$ index then for upcoming subarrays the behavior would become opposite (i.e. even 1s subarrays would act like odd 1s subarrays) wo we would do $$${x = n - i - x}$$$ where $$${n - i}$$$ is the number of subarrays starting with $$$ith$$$ index.

      So, we will sum-up all the no of subarrays with odd 1s for each bit (say $$$sum_i$$$).

      so our answer would be $$${\sum sum_i * 2 ^ i}$$$. here $$$2^i$$$ is the contribution of $$$ith$$$ bit.

      → Reply
      • »
        »
        »
        »
        4 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        I have a variation of this problem whose statement is as follows :
        You are given an array of int values, of length N. For a subarray it's score is defined as xor of all elements present in the subarray. Your goal is to choose any two non-overlapping subarrays such that sum of their scores is maximum possible. Print the maximum sum.

        How will You solve this problem ?

        Note: By non overlapping i mean : 0<=i1<=j1<i2<=j2<N

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, hide # ^ |
          ← Rev. 3  
          Vote: I like it 0 Vote: I do not like it

          I think we can easily do this problem using $$$Trie$$$ data structure as let say I am iterating on i [0...n-1] and storing all the $$$prefixs$$$ in the trie and at $$$ith$$$ index I would try to find the $$$maximumXor$$$ with current $$$prefix_i$$$ in the trie as

          $$${maximumXor = prefix_i}$$$ ^ $$${prefix_j, (0 \le j \lt i)}$$$

          which would give me $$$Xor$$$ of subarray [j...i]

          which would be the maximum xor subarray possible in [0...i]. and then I may store it in an array (say, $$$prefixMax$$$).

          where $$${prefixMax_i = max(maximumXor, prefixMax_{i - 1})}$$$ Similarly I may do this with suffix one as well after clearing the trie. so now we can find our answer as maximum over all $$${prefixMax_i + suffixMax_{i + 1}}$$$.

          UPD : My Code

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Btw can you share the problem link?

          → Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I actually just learned how to solve such problems. You should read a bit about the XOR basis, which basically lets you get a group of numbers of length at most the $$$MSB$$$ of the largest number in some array that can represent every $$$XORsum$$$ of every subsequence of numbers in some array. Furthermore, the group of numbers cannot represent a $$$XORsum$$$ that isn't present in the original array. In linear algebra, this is called a "basis" and, if I am understanding it correctly, there is a unique basis for each array, and you can find it using an $$$O(n \log A)$$$ algorithm detailed in the post.

So here's how you use it for this problem: first calculate the basis of the array, which has a length of at most $$$\log A$$$ more or less. Now once you get the basis, run an algorithm to generate all subsequences of the basis and find the $$$XORsums$$$ of all subsequences. Because of the interesting nature of the basis, each of these $$$XORsums$$$ are unique. Then just add them together and you get your answer.

The time complexity of finding the basis is $$$O(n \cdot \log A)$$$ and the time complexity of the subsequence generation is $$$O(2^{\log A})$$$ or just $$$O(A)$$$. So the total time complexity is $$$O(n\log A + A)$$$.

→ Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc365/submissions/67897489 easy to understand code , just checking for each bit in how many subarrays it will be counted

→ Reply