2
\$\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\$
3
  • 4
    \$\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, 2016 at 2:07
  • 3
    \$\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\$
    – r3mainer
    Feb 4, 2016 at 13:55
  • \$\begingroup\$ Thanks a lot for your comments. I'll revisit the problem with a fresh insight. \$\endgroup\$ Feb 4, 2016 at 16:04

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I see that we need a type of at least 50 unsigned bits, but no reason to restrict the code to run only on platforms that have an exactly 64-bit type. Remember that it's only provided if the platform directly supports the type (i.e. without any padding bits). \$\endgroup\$ Dec 2, 2022 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.