### PROBLEM LINK:

**Author:** Vitaliy Herasymiv

**Tester:** Tasnim Imran Sunny

**Editorialist:** Tuan Anh

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Bit Manipulation, Bitwise operation

### PROBLEM:

Given the array **A**[**1**…**N**] your mission is calculate the sum of **A**[**L**] xor **A**[**L** + **1**] xor … xor **A**[**R**] over all **1** ≤ **L** ≤ **R** ≤ **N**.

### QUICK EXPLANATION:

Let **S[i]** be the xor-sum of the first **i** numbers in the **A** array. Evidently, **S[0]** = **0**.

So we have: **A[L]** xor **A[L + 1]** xor **A[L + 2]** xor … xor **A[R]** = **S[R]** xor **S[L - 1]**.

Now the problem is reduced to calculate the sum of **S[R]** xor **S[L]** over all **0** ≤ **L** < **R** ≤ **N**.

To find the sum of **S[i]** xor **S[R]** for a given **R** such that **0** ≤ **i** < **R**, let us represent the numbers in their binary form and use column addition to add these numbers. Our sum will be in the following format:

S[0\] xor S[R] + S[1\] xor S[R] + ... + S[R - 1] xor S[R] (\*\)

We will calculate the number of 1’s in each column when adding all the numbers **S[0]**, **S[1]**, … , **S[R-1]**. Let **C[j]** be the number of 1’s in the jth column. If the jth bit of the corresponding **S[R]** is 0 then the total number of 1’s, leading to the sum, in the jth column will be **C[j]**, otherwise it will be **R** - **C[j]**.

Now, consider all the values of **R**, such that **0** < **R** ≤ **N**. For each **S[R]** we calculate the (*) sum based on the **C** value (the number of 1’s in each column) and after that we update **C**.

### DETAILED EXPLANATION:

XOR operation is a bitwise “Exclusive OR” operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains **0** in all positions where the corresponding bits coincide, and **1** on the rest of the positions.

For example, **3** XOR **5** = **011 _{2}** XOR

**101**=

_{2}**110**=

_{2}**6**.

And as explained in the problem statement, XOR-sum of a list of numbers is the result of XOR-ing all of them. XOR-sum of (**A[1]** XOR **A[2]** XOR … XOR **A[N]**) is defined as **A[1]** XOR (**A[2]** XOR (**A[3]** XOR ( … XOR **A[N]**))).

Let **S[i]** be the xor-sum of the first **i** numbers in the **A** array. Evidently, **S[0]** = **0**.

So, we have: **A[L]** xor **A[L + 1]** xor **A[L + 2]** xor … xor **A[R]** = **S[R]** xor **S[L - 1]**, **1** ≤ **L** ≤ **R** ≤ **N**.

RHS

= **S[R]** xor **S[L - 1] **

= **(A[1]** xor **A[2]** xor … xor **A[R]**) xor (**A[1]** xor **A[2]** xor … xor **A[L-1]**)

= **(A[1]** xor **A[2]** xor … xor **A[L-1]** xor **A[L]** xor … xor **A[R]**) xor (**A[1]** xor **A[2]** xor … xor **A[L-1]**)

= (**A[1]** xor **A[2]** xor … xor **A[L-1]**) xor (**A[L]** xor **A[L+1]** xor … xor **A[R]**) xor (**A[1]** xor **A[2]** xor … xor **A[L-1]**)

= 0 xor (**A[L]** xor **A[L+1]** xor … xor **A[R]**) [Since, a xor a = 0]

= **A[L]** xor **A[L+1]** xor … xor **A[R]** [Since, a xor 0 = a]

= LHS

Now the problem is reduced to calculate the sum of:

**S[R]** xor **S[L - 1]**, **1** ≤ **L** ≤ **R** ≤ **N**

or, **S[R]** xor **S[L]**, **0** ≤ **L** < **R** ≤ **N**

or, **S[L]** xor **S[R]**, **0** ≤ **L** < **R** ≤ **N**.

We can calculate the result in **O(N ^{2})** by consider all pair of

**L**and

**R**. However this is not good enough since

**N**can be

**100,000**so

**N**can be as large as

^{2}**10**.

^{10}We first iterate through **L**, to find the sum of **S[i]** xor **S[R]** for a given **R** such that **0** ≤ **i** < **R**, which we denote as (*). Let us represent the numbers in their binary form and use column addition to add these numbers. Our sum will be in the following format:

S[0\] xor S[R] + S[1\] xor S[R] + ... + S[R - 1] xor S[R] (\*\)

Let us first take a look at the process of column addition: Consider all the columns starting from the right most one. For each column, we add all the digits and the carry from the previous step to calculate the corresponding digit of the result and the new carry. We see that in the column addition we can calculate the result if we know all the digits in each column.

Our solution is based on the above approach. For now assume, we will simply add **S[0]**, **S[1]**, **S[2] **… **S[R-1]** using column addition to get the solution, ignoring the **S[R]**'s. We will calculate the number of 1’s in each column when adding all the numbers **S[0]**, **S[1]**, … , **S[R-1]** and let **C[j]** represent the number of **1**’s in the **jth** column.

**x xor S[R]** will help us identify the digits for * x* to be used for column addition to get the result. If the

**jth**bit of the corresponding

**S[R]**is

**0**then the total number of

**1**’s, leading to the sum, in the

**jth**column will be

**C[j]**, otherwise it will be

**R - C[j]**, since

**a xor 0 = a**and

**a xor 1 = a’**.

Now, consider all the values of **R, **such that **0** < **R** ≤ **N**. For each **S[R]** we calculate the (*) sum based on the **C** value (the number of **1**’s in each column) and after that we update **C**.

The complexity of this solution will be O(**N**log(max **S[i]**)). In **N** iterations we can calculate all the values of **S**, while in each iteration we will update the **C** and add the corresponding (*) for each **S[i]**, **1 ≤ i ≤ N**, to the final sum, complexity of which will be **O(log (S[i]))**.

**UPDATE: Let us take an example to better understand the Column addition as requested by some users.**

Let the array A = {3, 6, 7}.

Then as per the definition of xor-sum,

S[0] = 0; S[1] = 3; S[2] = 5; S[3] = 2.

Now let us calculate the (*) sum for S[R] where R = 3.

S[0\] xor S[3\] + S[1\] xor S[3\] + S[2\] xor S[3\] (\*\)

The binary representation of the same will be:

J_{2}J_{1}J_{0}0 0 0 xor 0 1 0 + 0 1 1 xor 0 1 0 + 1 0 1 xor 0 1 0 (\*\)

Now to calculate the (*) sum of this, we need to compute C_{j}(the number of 1’s in column J) for each column J.

For J = 2, C_{2} = 1, R - C_{2} = 2

For J = 1, C_{1} = 1, R - C_{1} = 2

For J = 0, C_{0} = 2, R - C_{0} = 1

Now, for computing the (*) Sum for S[R], we need to check the corresponding binary digit for S[R] before deciding whether we should consider C_{j} or (R - C_{j}) for Column J.

Here,

for J=2, the corresponding bit of S[R] (010) = 0, therefore, the value to be considered is C_{2} (since x xor 0 = x)

for J=1, the corresponding bit of S[R] (010) = 1, therefore, the value to be considered is R - C_{1} (since x xor 1 = x’)

for J=0, the corresponding bit of S[R] (010) = 0. therefore, the value to be considered is C_{0} (since x xor 0 = x)

Thus the (*) sum for S[3] will be:

C_{2} * (2^2) + (R - C_{1}) * (2^1) + C_{0} * (2^0) = 1 * 4 + 2 * 2 + 2 * 1 = 10.

Similarly we need to calculate the (*) sum for all 0 < R <= 3 and then add each of them to the result.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.