L8. XOR of Numbers in a Given Range | Bit Manipulation

This chapter covers an optimized approach to finding the bitwise XOR sum of numbers within a given range [L, R] in constant time $\mathcal{O}(1)$. By recognizing a repeating mathematical pattern in XOR sequences, we can bypass slow iterative loops and solve problems that would otherwise take linear time.

1. Problem Statement: XOR from 1 to $N$

The fundamental problem requires us to find the cumulative XOR sum of all integers from $1$ to a given integer $N$:

Example: $N = 4$

If we compute the XOR sum from $1$ to $4$:

2. Naive Approach vs. The Need for Optimization

The most intuitive way to solve this problem is to iterate from $1$ to $N$ using a loop, accumulating the XOR sum in a running variable.

Naive Implementation (Python)

def find_xor_naive(n: int) -> int:
    answer = 0
    for i in range(1, n + 1):
        answer ^= i
    return answer

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ because we iterate through every number from $1$ to $N$.
• Space Complexity: $\mathcal{O}(1)$ as we only maintain a single accumulator variable.

Note: While $\mathcal{O}(N)$ is acceptable for small inputs, an interviewer will immediately ask for an $\mathcal{O}(1)$ solution. Linear iteration is too slow when $N$ reaches constraints like $10^9$ or $10^{18}$.

3. Discovering the Hidden Repeating Pattern

To achieve $\mathcal{O}(1)$ time complexity, we must examine the outputs of $\text{XOR}(N)$ for consecutive values of $N$ to uncover a recurring mathematical cycle.

4. Breaking Down the Four-Step Cycle

Observing the table above reveals that the results repeat in a cycle of length 4 based on $N \pmod 4$:

1. If $N \pmod 4 == 1$: The result is always $1$.
   • Examples: $N=1 \rightarrow 1$, $N=5 \rightarrow 1$, $N=9 \rightarrow 1$.
2. If $N \pmod 4 == 2$: The result is always $N + 1$.
   • Examples: $N=2 \rightarrow 3$, $N=6 \rightarrow 7$, $N=10 \rightarrow 11$.
3. If $N \pmod 4 == 3$: The result is always $0$.
   • Examples: $N=3 \rightarrow 0$, $N=7 \rightarrow 0$.
4. If $N \pmod 4 == 0$: The result is always $N$ itself.
   • Examples: $N=4 \rightarrow 4$, $N=8 \rightarrow 8$, $N=12 \rightarrow 12$.

5. $\mathcal{O}(1)$ Implementation for $\text{XOR}(1 \dots N)$

Using our discovered modulo patterns, we can write a constant-time function to compute the XOR sum from $1$ to $N$.

Optimized Code (Python)

def compute_xor_from_one_to_n(n: int) -> int:
    remainder = n % 4
    if remainder == 1:
        return 1
    elif remainder == 2:
        return n + 1
    elif remainder == 3:
        return 0
    else:  # remainder == 0
        return n

Complexity Analysis

• Time Complexity: $\mathcal{O}(1)$ — executed via basic arithmetic and conditional checks.
• Space Complexity: $\mathcal{O}(1)$ — no additional data structures used.

6. Extending the Problem: XOR from Range $[L, R]$

Suppose the interviewer twists the problem: Instead of finding the XOR from $1$ to $N$, find the XOR sum of numbers in a given range from $L$ to $R$ inclusive:

Naive Range Approach

Iterating from $L$ to $R$ takes $\mathcal{O}(R - L + 1)$ time, which fails for large ranges. We need an $\mathcal{O}(1)$ approach.

7. Core Mental Model: The Cancellation Property

To achieve $\mathcal{O}(1)$ for a range $[L, R]$, we leverage two fundamental properties of the XOR operation ($\oplus$):

1. Self-Inverse Property: $X \oplus X = 0$ (Any number XORed with itself cancels out to zero).
2. Identity Property: $0 \oplus X = X$ (XORing with zero leaves the number unchanged).

Real-Life Analogy: The Prefix Cancellation Workflow

Imagine you have a full sequence of numbers from $1$ to $R$, and you want to isolate only the subset from $L$ to $R$.

• If you compute $\text{XOR}(1 \dots R)$, you have all numbers from $1$ up to $R$.
• If you compute $\text{XOR}(1 \dots L-1)$, you have the prefix numbers that you don't want.
• If you XOR these two results together—XOR(1 ... R) ^ XOR(1 ... L-1)—all numbers belonging to the unwanted prefix ($1$ through $L-1$) appear twice and cancel each other out ($X \oplus X = 0$).

Step-by-Step Walkthrough ($L = 4, R = 7$)

1. Compute $\text{XOR}(1 \dots 3) = 1 \oplus 2 \oplus 3 = 0$.
2. Compute $\text{XOR}(1 \dots 7) = 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus 7 = 0$.
3. Perform XOR of both results: $\text{XOR}(1 \dots 3) \oplus \text{XOR}(1 \dots 7) = 0 \oplus 0 = 4$.
   • Behind the scenes: $(1 \oplus 1) \oplus (2 \oplus 2) \oplus (3 \oplus 3) \oplus 4 \oplus 5 \oplus 6 \oplus 7 = 4 \oplus 5 \oplus 6 \oplus 7$.

8. Complete Range XOR Implementation

Here is the final consolidated function to solve the range XOR query in $\mathcal{O}(1)$ time.

def compute_xor_from_one_to_n(n: int) -> int:
    remainder = n % 4
    if remainder == 1:
        return 1
    elif remainder == 2:
        return n + 1
    elif remainder == 3:
        return 0
    else:
        return n

def range_xor(l: int, r: int) -> int:
    # XOR(L to R) = XOR(1 to L-1) ^ XOR(1 to R)
    return compute_xor_from_one_to_n(l - 1) ^ compute_xor_from_one_to_n(r)

# Example execution:
# For L = 4, R = 7
print(range_xor(4, 7))  # Output: 4

Summary and Key Takeaways

• Bitwise XOR Property ($\mathcal{O}(1)$ Cancellation): Identical numbers XORed together cancel out to zero ($X \oplus X = 0$), while XORing with zero preserves the value ($0 \oplus X = X$).
• Linear Iteration Bottleneck: A naive loop from $1$ to $N$ or $L$ to $R$ operates in $\mathcal{O}(N)$ or $\mathcal{O}(R - L + 1)$ time, which is inefficient for large constraints.
• Repeating Modulo Cycle: The XOR sum of numbers from $1$ to $N$ follows a repeating 4-step cycle based on $N \pmod 4$:
  • $N \pmod 4 == 1 \rightarrow \text{Result} = 1$
  • $N \pmod 4 == 2 \rightarrow \text{Result} = N + 1$
  • $N \pmod 4 == 3 \rightarrow \text{Result} = 0$
  • $N \pmod 4 == 0 \rightarrow \text{Result} = N$
• Constant Time Range Queries: Any range XOR query from $L$ to $R$ can be transformed into $\text{XOR}(1 \dots L-1) \oplus \text{XOR}(1 \dots R)$.
• Optimal Complexity: Both the single-number cumulative XOR and the range XOR algorithms achieve optimal $\mathcal{O}(1)$ time complexity and $\mathcal{O}(1)$ space complexity.