# HackerRank: XOR-sequence

I am trying to solve the following problem at HackerRank:

## XOR-Sequence

An array, $A$, is defined as follows:

• $A_0 = 0$
• $A_x = A_{x-1} \oplus x$ for $x>0$, where $\oplus$ is the symbol for XOR

You must answer $Q$ questions. Each $i^{th}$ question is in the form $L_i\ R_i$, and the answer is $A_{L_i} \oplus A_{L_i+1} \oplus \ldots \oplus A_{R_i-1} \oplus A_{R_i}$ (the Xor-Sum of segment $[Li,Ri]$).

Print the answer to each question.

### Input Format

The first line contains $Q$ (the number of questions).
The $Q$ subsequent lines each contain two space separated integers, $L$ and $R$, respectively. Line $i$ contains $L_i$ and $R_i$.

### Constraints

$1 \le Q \le 10^5$
$1 \le L_i \le R_i \le 10^{15}$

My code is correct, but it's slow. It really starts slowing down once I reach numbers like 269 million for the array index. The max array index can be 1015, so it will be really slow. What things can I do to increase the speed?

#include <iostream>

int main() {
int N;
int64_t f_index, l_index;

std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> f_index >> l_index;
int64_t sum = 0;
int64_t temp;
for (int64_t index = f_index; index <= l_index; ++index) {
if (index%4 == 0) {
temp = sum^index;
sum = temp;
} else if (index%4 == 1) {
temp = sum^1;
sum = temp;
} else if (index%4 == 2) {
temp = sum^(index + 1);
sum = temp;
} else if (index%4 == 3) {
temp = sum^0;
sum = temp;
}
}
std::cout << sum << std::endl;
}
return 0;
}

• For inputs of size $10^{15}$, you are doomed if you use a linear algorithm. You want to go back to the drawing board and find a more efficient way to do things. You've worked out a nice pattern for the terms of A_n, now you just need to aggregate them efficiently. HInt: start by thinking about how you can efficiently compute the XOR sum of [1, (1<<50)-1]? What about [(1<<50),(1<<50)+(1<<25)+1]? – Erick Wong Feb 4 '16 at 2:07
• Please add a summary of the challenge being solved, not just a link. – 200_success Feb 4 '16 at 8:41
• Just to elaborate on the comment by @ErickWong: If you can find a pattern that gives you the Xor-Sum of the range [0,N], then you can easily calculate the Xor-Sum of any range as Xor-Sum(0,L−1) ⊕ Xor-Sum(0,R). If you just print out a few terms of the series, you'll discover the pattern soon enough. – squeamish ossifrage Feb 4 '16 at 13:55
• Thanks a lot for your comments. I'll revisit the problem with a fresh insight. – Ankit Sharma Feb 4 '16 at 16:04