0
$\begingroup$

I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

Problem Statement

XOR-sum of a sub-array is to XOR all the numbers of that sub-array. An array is given to you, you have to add all possible such XOR-sub-array.

Example

Input

Array :- 1 2

Output :- 6

Explanation

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

for (int i=0, p=1; i<30; i++, p<<=1) {
    int c=0;
    for (int j=0; j<=N; j++) {
        if (A[j]&p) c++;
    }
    ret+=(long long)c*(N-c+1)*p;
}

In pseudocode:

  • Set $r = 0$
  • For $i$ from $0$ to $29$, let $p = 2^i$.
    • Set $c=0$
    • Iterate over the array $A$. For each element $A[j]$:
      • If $A[j] \mathbin\& p \ne 0$ then increment $c$. ($\&$ is bitwise and.)
    • Add $c \times (N-c+1) \times p$ to $r$
$\endgroup$
  • $\begingroup$ @D.W. I just want help. I put lots of time on this. At the end, I got stuck. Please help me to put out from here, $\endgroup$ – devsda Nov 21 '13 at 5:20
  • $\begingroup$ @D.W. If you can, shift this question to SO. $\endgroup$ – devsda Nov 21 '13 at 5:27
  • $\begingroup$ @devsda There's an answer which explains the algorithm, and it uses mathematical formatting. I don't think this question needs to be migrated, and the answer can't be. If you need help with the code part, ask on Stack Overflow. $\endgroup$ – Gilles Nov 21 '13 at 12:12
  • $\begingroup$ see also math.stackexchange.com/questions/712487/… $\endgroup$ – Andre Holzner Aug 14 '16 at 14:10
4
$\begingroup$

After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A[j]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A[i-1]$ is $1$ and the same bit in $A[j]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A[i-1]$ and $1$ for $A[j]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k[i-1],A^k[j])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.

$\endgroup$
  • $\begingroup$ Then , why i only moves upto 30, Any logic ? $\endgroup$ – devsda Nov 21 '13 at 5:47
  • $\begingroup$ Can you please explain the whole logic ? How this logic comes in mind, as I am naive. $\endgroup$ – devsda Nov 21 '13 at 5:58
  • $\begingroup$ It'll help to start with an example of one bit numbers and see what really happens. Then extend it to two bits etc. $\endgroup$ – Parham Nov 21 '13 at 6:59
  • $\begingroup$ You didn't give my first question's answer. $\endgroup$ – devsda Nov 21 '13 at 8:49
  • $\begingroup$ ok. Instead of calculating XORs for all possible subarray and then summing them up (which is the naive solution), we count the number of subarrays which $k$th bit of their XOR is 1. This bit adds $2^k$ to the total sum. $c.(N-c)$ is the number of such subarrays. Is it clear now? $\endgroup$ – Parham Nov 21 '13 at 10:03
-1
$\begingroup$

Just do the OR operations of all numbers and multiply the answer with power(2,N-1) where N is the length of your array.
For array given in question: 1 OR 2 = 3 Now, 3*(power(2,(2-1))) = 6 which is the answer.
The point here is that, Each set bit of any number occurs exactly in power(2,N-1) sub arrays.

$\endgroup$
  • $\begingroup$ How does this answer the question? The question asks to understand what's going on in a particular solution. It sounds like you're proposing a different solution. Would you consider editing your answer to make it clearer how it answers the question that was asked? $\endgroup$ – D.W. Sep 9 '15 at 16:22
  • $\begingroup$ Question line also says that "I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here." $\endgroup$ – Vedsar Kushwaha Sep 9 '15 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.