Find XOR of Numbers from L to R

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.

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 10⁹.

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.

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)

#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;
}

#include <iostream>
using namespace std;

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; // never reached
}

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

int main() {
    int L = 3, R = 9;
    int result = xorRange(L, R);
    cout << "XOR from " << L << " to " << R << " is " << result << endl;
    return 0;
}

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

def xor_range(L, R):
    return xor_from_0_to(R) ^ xor_from_0_to(L - 1)

L, R = 3, 9
result = xor_range(L, R)
print(f"XOR from {L} to {R} is {result}")

public class XorRange {
    public static int xorFrom0To(int n) {
        switch (n % 4) {
            case 0: return n;
            case 1: return 1;
            case 2: return n + 1;
            case 3: return 0;
            default: return 0;
        }
    }

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

    public static void main(String[] args) {
        int L = 3, R = 9;
        int result = xorRange(L, R);
        System.out.println("XOR from " + L + " to " + R + " is " + result);
    }
}

function xorFrom0To(n) {
  switch (n % 4) {
    case 0: return n;
    case 1: return 1;
    case 2: return n + 1;
    case 3: return 0;
  }
}

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

const L = 3, R = 9;
const result = xorRange(L, R);
console.log(`XOR from ${L} to ${R} is ${result}`);

package main

import "fmt"

func xorFrom0To(n int) int {
    switch n % 4 {
    case 0:
        return n
    case 1:
        return 1
    case 2:
        return n + 1
    case 3:
        return 0
    }
    return 0
}

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

func main() {
    L, R := 3, 9
    result := xorRange(L, R)
    fmt.Printf("XOR from %d to %d is %d\n", L, R, result)
}

fn xor_from_0_to(n: u32) -> u32 {
    match n % 4 {
        0 => n,
        1 => 1,
        2 => n + 1,
        3 => 0,
        _ => 0,
    }
}

fn xor_range(L: u32, R: u32) -> u32 {
    xor_from_0_to(R) ^ xor_from_0_to(L - 1)
}

fn main() {
    let L = 3;
    let R = 9;
    let result = xor_range(L, R);
    println!("XOR from {} to {} is {}", L, R, result);
}

fun xorFrom0To(n: Int): Int = when (n % 4) {
    0 -> n
    1 -> 1
    2 -> n + 1
    else -> 0
}

fun xorRange(L: Int, R: Int): Int {
    return xorFrom0To(R) xor xorFrom0To(L - 1)
}

fun main() {
    val L = 3
    val R = 9
    val result = xorRange(L, R)
    println("XOR from $L to $R is $result")
}

func xorFrom0To(_ n: Int) -> Int {
    switch n % 4 {
    case 0: return n
    case 1: return 1
    case 2: return n + 1
    case 3: return 0
    default: return 0
    }
}

func xorRange(_ L: Int, _ R: Int) -> Int {
    return xorFrom0To(R) ^ xorFrom0To(L - 1)
}

let L = 3
let R = 9
let result = xorRange(L, R)
print("XOR from \(L) to \(R) is \(result)")

function xorFrom0To(n: number): number {
  switch (n % 4) {
    case 0: return n;
    case 1: return 1;
    case 2: return n + 1;
    case 3: return 0;
  }
  return 0;
}

function xorRange(L: number, R: number): number {
  return xorFrom0To(R) ^ xorFrom0To(L - 1);
}

const L = 3, R = 9;
const result = xorRange(L, R);
console.log(`XOR from ${L} to ${R} is ${result}`);

Time complexity

Space complexity

O(1)

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