Find XOR of Numbers from L to R - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given two integers L and R, compute the XOR of all numbers in the inclusive range [L, R].

That is, return the result of: L ^ (L+1) ^ (L+2) ^ ... ^ R

The goal is to perform this efficiently without looping through every number.

Examples❯

L R Output Description
3 9 10 XOR from 3 to 9 is 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 10
0 4 4 XOR from 0 to 4 is same as xorFrom0To(4) = 4
5 5 5 Only one number in range, XOR is 5
7 7 7 XOR of single number 7 is 7
10 15 5 XOR from 10 to 15 = xorFrom0To(15) ^ xorFrom0To(9) = 0 ^ 5 = 5
0 0 0 XOR from 0 to 0 is 0
1000 10000 10236 Large range, computed using xorFrom0To(10000) ^ xorFrom0To(999)
"" 10 10 Empty L is treated as 0; xorFrom0To(10) ^ xorFrom0To(-1) = 10 ^ 0 = 10
5 "" 5 Empty R is treated as 0; range becomes [5, 0], treated as xorFrom0To(0) ^ xorFrom0To(4) = 0 ^ 4 = 4
"" "" 0 Both empty, treated as 0 to 0 → xor is 0

Solution❯

Understanding the Problem

We are given two integers L and R, and we need to compute the XOR of all integers from L to R (inclusive).

Mathematically, this is written as: L ^ (L+1) ^ (L+2) ^ ... ^ R. At first glance, it might seem like we need to loop through every number in this range and apply XOR. But for large ranges, that would be inefficient.

Instead, we’ll use a mathematical pattern observed in the XOR of numbers from 0 to n to compute the result efficiently.

Step-by-Step Solution with Example

Step 1: Understand XOR Pattern from 0 to n

The XOR from 0 to n follows a repeating pattern every 4 numbers:

  • If n % 4 == 0, then xor(0 to n) = n
  • If n % 4 == 1, then xor(0 to n) = 1
  • If n % 4 == 2, then xor(0 to n) = n + 1
  • If n % 4 == 3, then xor(0 to n) = 0

This means we can compute the XOR of numbers from 0 to any number n in constant time.

Step 2: Create the helper function

def xorFrom0To(n):
    if n % 4 == 0:
        return n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return n + 1
    else:
        return 0

Step 3: Compute XOR from L to R

Using the helper, we calculate xor(L to R) as:

xor(L to R) = xor(0 to R) ^ xor(0 to L-1)

Step 4: Apply it on an Example

Let’s say L = 3 and R = 9

First compute:

  • xorFrom0To(9) = 1 (since 9 % 4 == 1)
  • xorFrom0To(2) = 3 (since 2 % 4 == 2 → 2 + 1)

So the final answer is 1 ^ 3 = 2

Edge Cases

  • L == R: We are XORing only one number, so the answer is just L (or R).
  • L == 0: Then we directly compute xorFrom0To(R) since xor(0 to -1) is 0.
  • Very large values: Since the solution uses mathematical computation, it works efficiently even for L and R in the order of 109.

Final Thoughts

This problem highlights how mathematical patterns can help avoid brute-force solutions. XOR is a powerful operator with useful properties, and recognizing repeating patterns allows us to solve such range queries in constant time.

Always try to analyze the mathematical nature of the problem before jumping to code—this often leads to elegant and optimal solutions.

Algorithm Steps❯

  1. Define a helper function xorFrom0To(n) that returns the XOR of all numbers from 0 to n.
  2. This function uses the known pattern:
    n % 4 == 0 → n
    n % 4 == 1 → 1
    n % 4 == 2 → n + 1
    n % 4 == 3 → 0
  3. Then compute the XOR from L to R as:
    xorFrom0To(R) ^ xorFrom0To(L - 1)

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int xorFrom0To(int n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0; // should never reach here
}

int xorRange(int L, int R) {
    return xorFrom0To(R) ^ xorFrom0To(L - 1);
}

int main() {
    int L = 3, R = 9;
    int result = xorRange(L, R);
    printf("XOR from %d to %d is %d\n", L, R, result);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The algorithm uses a mathematical pattern to directly compute the XOR from 0 to L-1 and from 0 to R, both in constant time. There are no loops or recursive calls involved.
Average CaseO(1)Regardless of the size of the range [L, R], the XOR is computed using two constant-time operations: xorFrom0To(R) and xorFrom0To(L - 1).
Worst CaseO(1)Even when the range [L, R] is very large, the algorithm does not iterate over the numbers. It leverages a modulo-4 pattern for constant-time calculation.

Space Complexity❯

O(1)

Explanation: The solution uses only a fixed number of variables to store intermediate XOR values. No additional memory is required regardless of the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...