demons_paw's blog

Sum of XOR sum of all subsets of an array.
By demons_paw, history, 22 months ago, In English

Given an array of size $$$n$$$. How can we find sum of XOR sum of all subsets in better than $$$O(2^n)$$$ ?
For example consider $$$array = [1,4,5]$$$
$$$ Answer = 1 + 4 + 5 + 1^4 + 1^5 + 4^5 + 1^4^5 $$$ (here '^' denotes bitwise XOR )

Basically harder version of this leetcode problem, with nums.length <= 10^5.

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

Comments Comments (9)
| Write comment?
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

consider for each individual bit let's say i if for any of the elements in the array we count the number of ones that are there now we will only add the ith position as 2*(i+1) now as there are lets say k ones so there must be (n-k) zeros now for the position to have xor value of one we will have to choose odd number of ones so it would be : kc1+kc3+...+kck=2**(k-1) now we can choose any number of zeros with each of the chossen pair so it would be (n-k)c0+(n-k)c1+(n-k)c2.....=2**(n-k) then we multiply then to get 2**(n-1) so answer would be : pow(2,n-1)*(pow(2,i)) for all position i where i is a set bit at least once in the array (https://mirror.codeforces.com/problemset/problem/1614/C)https://mirror.codeforces.com/problemset/problem/1614/C

sorry for a bad explanation you can try the above problem for a greater understanding

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Consider each bit independently. For the $$$i$$$-th bit, let's say there are $$$k$$$ elements that have that bit as $$$1$$$, and $$$n-k$$$ elements that do not.

Then, the contribution to the answer is $$$2^i \times \left( \sum_{j=0}^{\left \lfloor \frac{k-1}{2} \right \rfloor} {k \choose 2j+1} \cdot 2^{n-k} \right) = 2^i \times 2^{n-1}$$$.

Time complexity: $$$O(n \log \max(a_i))$$$.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    On observing you can realise that answer is just $$$x \cdot 2^{n-1}$$$, where $$$x$$$ is bitwise OR of all elements of the given array.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I don't understand. Can you prove it?

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        The expression simplifies to $$$2^i \cdot 2^{n-1}$$$ for each bit which appears atleast once in any number in the array.

        So the total sum is $$$x \cdot 2^{n-1}$$$ where $$$x$$$ is OR of the array.

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          I don't understand why we can simplify from $$$2^i \times \left( \sum_{j=0}^{\left \lfloor \frac{k-1}{2} \right \rfloor} {k \choose 2j+1} \cdot 2^{n-k} \right) $$$ to $$$2^i \cdot 2^{n-1}$$$, xor value of a position = 1 only when the number of set bits is odd

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            $$$\sum_{j=0}^{\left\lfloor {\frac{k-1}{2}}\right \rfloor}\binom{k}{2j+1}=2^{k-1}$$$

            → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah you are correct

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

A similiar codeforces problem — Round 757 Div. 2 C Divan and bitwise operations

→ Reply