HackerRank: XOR-sequence

Question

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 10¹⁵, 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;
}

Answer 1

This code is missing a declaration for int64_t. I'm assuming you intended

#include <cstdint>
using std::int64_t;

That said, I'd skip the using and just write the full type name where we need it.

It's not clear why we're using signed types for our arithmetic, nor why we need our values to be exactly 64 bits. I suggest std::uint_fast16_t for N and std::uint_fast64_t for the values.

We're missing the usual check that >> was successful before using the values we read.

We have an unnecessary flush after each write because we're using std::endl instead of '\n'.

The temp variable is unnecessary: temp = sum ^ x; sum = temp; can be replaced by sum ^= x;.

The chain of if (index % 4) tests would be clearer as a switch.

---

These correctness and readability fixes get us to

#include <cstdint>
#include <iostream>

using value_t = std::uint_fast64_t;

static auto sum_xor_sequence(value_t left, value_t right)
{
    value_t sum = 0;
    for (value_t i = left;  i <= right;  ++i) {
        switch (i % 4) {
        case 0:
            sum ^= i;
            break;
        case 1:
            sum ^= 1;
            break;
        case 2:
            sum ^= i + 1;
            break;
        case 3:
            // nothing
            break;
        }
    }
    return sum;
}

#if USING_GTEST

#include <gtest/gtest.h>

TEST(xorsum, simple)
{
    EXPECT_EQ(sum_xor_sequence(0, 5), 7);
    EXPECT_EQ(sum_xor_sequence(0, 1), 1);
    EXPECT_EQ(sum_xor_sequence(2, 5), 6);
}

#else

int main()
{
    using count_t = std::uint_fast16_t;

    count_t N;
    std::cin >> N;
    if (!std::cin) {
        return 1;
    }

    for (count_t i = 0;  i < N;  ++i) {
        value_t l, r;
        std::cin >> l >> r;
        if (!std::cin) {
            return 1;
        }
        std::cout << sum_xor_sequence(l, r) << '\n';
    }
    return 0;
}

#endif

---

To improve the performance, we need to get rid of the for loop that may execute for up to 10¹⁵ iterations each time. This should be quite straightforward if we derive a formula for sum_xor_sequence(0, x), since we know that we can use a single ⊕ operation on two of those to get the value for a subrange - as demonstrated in the unit test above: f(a,b)≡ f(0,a-1) ⊕ f(0,b).

The derivation of this should be fairly similar to the process used to determine the values in the switch from the series definition.