1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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]? \$\endgroup\$ – Erick Wong Feb 4 '16 at 2:07
  • 1
    \$\begingroup\$ Please add a summary of the challenge being solved, not just a link. \$\endgroup\$ – 200_success Feb 4 '16 at 8:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – squeamish ossifrage Feb 4 '16 at 13:55
  • \$\begingroup\$ Thanks a lot for your comments. I'll revisit the problem with a fresh insight. \$\endgroup\$ – Ankit Sharma Feb 4 '16 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.