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 = 0112 XOR 1012 = 1102 = 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(N2) by consider all pair of L and R. However this is not good enough since N can be 100,000 so N2 can be as large as 1010.
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(Nlog(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:
J2 J1 J0 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 Cj(the number of 1’s in column J) for each column J.
For J = 2, C2 = 1, R - C2 = 2
For J = 1, C1 = 1, R - C1 = 2
For J = 0, C0 = 2, R - C0 = 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 Cj or (R - Cj) for Column J.
Here,
for J=2, the corresponding bit of S[R] (010) = 0, therefore, the value to be considered is C2 (since x xor 0 = x)
for J=1, the corresponding bit of S[R] (010) = 1, therefore, the value to be considered is R - C1 (since x xor 1 = x’)
for J=0, the corresponding bit of S[R] (010) = 0. therefore, the value to be considered is C0 (since x xor 0 = x)
Thus the (*) sum for S[3] will be:
C2 * (2^2) + (R - C1) * (2^1) + C0 * (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.