Why does prefix XOR repeat based on N % 4?

The XOR of consecutive integers forms a repeating four-case pattern. Therefore, the result for 0 to N depends only on the remainder when N is divided by 4.

What happens when L = 0?

Then L - 1 = -1. Defining prefixXOR(N) = 0 for N < 0 makes the same formula work without needing a separate special case.

Why can XOR cancel the prefix while normal subtraction cannot be used?

XOR is its own inverse. Since x ^ x = 0, XORing the same group of values twice removes their contribution.

Does the same four-case pattern work for bitwise AND or OR?

No. This pattern specifically comes from the behavior of XOR over consecutive integers and does not apply directly to bitwise AND or OR.

Why is the Optimal Approach better than traversing the complete range?

The Brute Force Approach performs one XOR for every value between L and R, while the prefix-pattern approach requires only a constant number of operations regardless of the range size.

XOR of Numbers in a Range L to R

Q: Why do we use prefixXOR(R) ^ prefixXOR(L - 1)?

prefixXOR(R) contains every value from 0 to R, while prefixXOR(L - 1) contains the values before L. XORing them makes the common prefix appear twice, so those values cancel and only the range L to R remains.

Q: Why can XOR cancel the prefix while normal subtraction cannot be used?

XOR is its own inverse. Since x ^ x = 0, XORing the same group of values twice removes their contribution.

Q: Does the same four-case pattern work for bitwise AND or OR?

No. This pattern specifically comes from the behavior of XOR over consecutive integers and does not apply directly to bitwise AND or OR.

Q: Why is the Optimal Approach better than traversing the complete range?

The Brute Force Approach performs one XOR for every value between L and R, while the prefix-pattern approach requires only a constant number of operations regardless of the range size.

Given two non-negative integers L and R, return the bitwise XOR of all integers in the inclusive range from L to R.

Example 1

Input: L = 4, R = 8

Output: 8

Explanation: The numbers in the range are 4, 5, 6, 7, and 8. The operation is 4 ^ 5 ^ 6 ^ 7 ^ 8. Calculating this sequentially gives a final result of 8.

Example 2

Input: L = 3, R = 4

Output: 7

Explanation: The only numbers in the range are 3 and 4. The operation 3 ^ 4 evaluates to 7.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

The most direct approach is to process every number in the required range and keep XORing it with a running result.

Starting with 0 is useful because x ^ 0 = x. After every value from L to R has been included, the running XOR represents the XOR of the complete range.

Algorithm

If L > R, return 0 because the given range is invalid.
Initialize result = 0 to store the cumulative XOR of the numbers processed so far.
Traverse every integer i from L to R, inclusive.
Update result as result ^ i so the current number becomes part of the range XOR.
Return result after every number in the range has been processed.

Dry Run

XOR of Numbers in Range Brute Force Appraoch Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    long long findRangeXOR(long long L, long long R) {
7        if (L > R) {
8            return 0;
9        }
10
11        long long result = 0;
12
13        /*
14         * Include every value in the range once so result
15         * gradually becomes the XOR from L through R.
16         */
17        for (long long value = L; value <= R; value++) {
18            result ^= value;
19        }
20
21        return result;
22    }
23};
24
25int main() {
26    long long L = 3;
27    long long R = 6;
28
29    Solution solution;
30    cout << solution.findRangeXOR(L, R) << endl;
31
32    return 0;
33}

Complexity Analysis

Time Complexity: O(R - L + 1), because every integer in the range is processed once.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

Computing every value in the range is unnecessary because the XOR from 0 to any number N follows a repeating pattern based on N % 4.

Let:

prefixXOR(N) = 0 ^ 1 ^ 2 ^ ... ^ N

Then the XOR of the range L to R can be obtained as:

prefixXOR(R) ^ prefixXOR(L - 1)

This works because every value from 0 to L - 1 appears in both prefix XORs. XORing the two results cancels those common values using x ^ x = 0, leaving only the numbers from L to R.

The prefix XOR follows this four-case pattern:

If N % 4 == 0, prefixXOR(N) = N
If N % 4 == 1, prefixXOR(N) = 1
If N % 4 == 2, prefixXOR(N) = N + 1
If N % 4 == 3, prefixXOR(N) = 0

Because this pattern gives a prefix XOR in constant time, the complete range XOR can also be found in constant time.

Algorithm

If L > R, return 0 because the range is invalid.
Create a helper function prefixXOR(N) that returns the XOR of all integers from 0 to N.
If N < 0, return 0. This handles L = 0, where the second prefix becomes prefixXOR(-1).
Inside the helper, calculate N % 4 and return the corresponding value from the four-case XOR pattern.
Calculate prefixXOR(R) to represent the XOR of all values from 0 to R.
XOR it with prefixXOR(L - 1). The common prefix cancels, leaving exactly the XOR from L to R.

Dry Run

XOR of Numbers in Range Optimal Appraoch Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5private:
6    long long prefixXOR(long long n) {
7        /*
8         * This represents an empty prefix and also allows
9         * the same range formula to work when L is 0.
10         */
11        if (n < 0) {
12            return 0;
13        }
14
15        long long remainder = n % 4;
16
17        /*
18         * XOR from 0 through n follows a four-case pattern,
19         * so only n % 4 is needed to determine the result.
20         */
21        if (remainder == 0) {
22            return n;
23        }
24
25        if (remainder == 1) {
26            return 1;
27        }
28
29        if (remainder == 2) {
30            return n + 1;
31        }
32
33        return 0;
34    }
35
36public:
37    long long findRangeXOR(long long L, long long R) {
38        if (L > R) {
39            return 0;
40        }
41
42        /*
43         * The prefix before L appears in both XOR groups
44         * and cancels, leaving only values from L through R.
45         */
46        return prefixXOR(R) ^ prefixXOR(L - 1);
47    }
48};
49
50int main() {
51    long long L = 3;
52    long long R = 6;
53
54    Solution solution;
55    cout << solution.findRangeXOR(L, R) << endl;
56
57    return 0;
58}

Complexity Analysis

Time Complexity: O(1), because each prefix XOR is found using a fixed number of arithmetic and bitwise operations.

Space Complexity: O(1), because no additional data structure is required.

Interview follow-up Questions

prefixXOR(R) contains every value from 0 to R, while prefixXOR(L - 1) contains the values before L. XORing them makes the common prefix appear twice, so those values cancel and only the range L to R remains.

XOR of Numbers in a Range L to R

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Check Even or Odd

BIT Basics and Operators

XOR Basics