1. Introduction
The XOR of Number Range is a Bit Manipulation problem.
In this problem, we are given two integers l and r. We need to calculate the bitwise XOR of all integers between l and r, including both endpoints.
Instead of using a loop to calculate the XOR of every number, we can solve this problem using a mathematical pattern.
This approach takes O(1) time and O(1) auxiliary space.
2. What is XOR?
XOR stands for Exclusive OR.
It is a bitwise operator that compares two binary numbers bit by bit.
The XOR operator returns:
- 0 when both bits are the same.
- 1 when both bits are different.
XOR Truth Table
In C#, we use the ^ operator to perform XOR.
Example
Let's calculate:
5 ^ 3
Binary representation:
5 = 101
3 = 011
---
110 = 6
Output:
6
Therefore:
5 ^ 3 = 6
3. Important Properties of XOR
Before solving the problem, understand these four important properties.
Property 1: Same number XOR gives zero
5 ^ 5 = 0
Property 2: XOR with zero gives the same number
5 ^ 0 = 5
Property 3: Commutative property
The order of numbers does not change the result.
5 ^ 3 = 3 ^ 5
Property 4: Associative property
We can change the grouping without changing the result.
(5 ^ 3) ^ 2 = 5 ^ (3 ^ 2)
These properties help us simplify range XOR calculations.
4. Understanding the Problem
Given two integers:
l = 4
r = 8
We need to calculate:
4 ^ 5 ^ 6 ^ 7 ^ 8
Step-by-step:
4 ^ 5 = 1
1 ^ 6 = 7
7 ^ 7 = 0
0 ^ 8 = 8
Final output:
8
5. Brute Force Approach
The simplest approach is to use a loop.
public int findXOR(int l, int r)
{
int result = 0;
for (int i = l; i <= r; i++)
{
result ^= i;
}
return result;
}
Explanation
- Initialize
result = 0. - Start a loop from
l to r. - Perform XOR between the current number and
result. - Return the final XOR value.
Complexity
- Time Complexity: O(r - l + 1)
- Auxiliary Space: O(1)
This works, but it can be inefficient when the range is very large.
6. Optimized Approach – Mathematical Pattern
We can calculate the XOR from 0 to any number n using a repeating pattern.
Observe these calculations:
n | XOR (0 to n) | Result |
|---|
0 | 0 | 0 |
1 | 0 ^ 1 | 1 |
2 | 0 ^ 1 ^ 2 | 3 |
3 | 0 ^ 1 ^ 2 ^ 3 | 0 |
4 | 0 ^ 1 ^ 2 ^ 3 ^ 4 | 4 |
5 | 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 | 1 |
6 | 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 | 7 |
7 | 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 | 0 |
We can see that the result repeats every four numbers.
Four Mathematical Conditions
Condition | Result |
|---|
n % 4 == 0 | n |
n % 4 == 1 | 1 |
n % 4 == 2 | n + 1 |
n % 4 == 3 | 0 |
This pattern allows us to calculate the prefix XOR in constant time.
7. How to Calculate XOR Between l and r?
The important formula is:
XOR(l, r) = XOR(0, r) ^ XOR(0, l - 1)
Why does this work?
Consider:
XOR(0, 8) = 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8
XOR(0, 3) = 0 ^ 1 ^ 2 ^ 3
When we XOR these two results, the common numbers cancel because:
a ^ a = 0
Therefore, only the numbers from 4 to 8 remain.
XOR(4, 8) = XOR(0, 8) ^ XOR(0, 3)
= 8 ^ 0
= 8
8. Optimized C# Solution
class Solution
{
public int findXOR(int l, int r)
{
return XOR(r) ^ XOR(l - 1);
}
private int XOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
return 0;
}
}
9. Code Explanation
Step 1: Main Method
public int findXOR(int l, int r)
{
return XOR(r) ^ XOR(l - 1);
}
This method calculates the XOR of the given range.
XOR(r) calculates XOR from 0 to r.XOR(l - 1) calculates XOR from 0 to l - 1.- Finally, XOR both results to get the required range.
Step 2: Helper Method
private int XOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
return 0;
}
This method calculates XOR from 0 to n using four conditions.
Condition 1:
if (n % 4 == 0)
return n;
When the remainder is 0, return n.
Condition 2:
if (n % 4 == 1)
return 1;
When the remainder is 1, return 1.
Condition 3:
if (n % 4 == 2)
return n + 1;
When the remainder is 2, return n + 1.
Condition 4:
return 0;
When the remainder is 3, return 0.
10. Dry Run
Input:
l = 5
r = 9
Step 1:
XOR(9)
9 % 4 = 1
Result = 1
Step 2:
XOR(4)
4 % 4 = 0
Result = 4
Step 3:
XOR(5, 9)
= XOR(9) ^ XOR(4)
= 1 ^ 4
= 5
Output:
5
11. Complexity Analysis
Approach | Time Complexity | Auxiliary Space |
|---|
Brute Force | O(r - l + 1) | O(1) |
Optimized | O(1) | O(1) |
The optimized approach is better because it uses a fixed number of operations regardless of the range size.
12. Important Interview Takeaways
- XOR of two identical numbers is zero.
- XOR with zero returns the same number.
- XOR is useful for identifying repeated and missing numbers.
- Prefix XOR can simplify range XOR problems.
- The XOR pattern repeats every four numbers.
- Use the formula
XOR(l, r) = XOR(0, r) ^ XOR(0, l - 1) to solve range queries efficiently.
13. Conclusion
The XOR of Number Range problem teaches us how mathematical patterns and bit manipulation can optimize a simple looping solution.
The main idea is to calculate prefix XOR using the modulo 4 pattern and then subtract the unwanted prefix using XOR.
Remember this formula:
XOR(l, r) = XOR(r) ^ XOR(l - 1)
With this technique, we achieve O(1) time and O(1) auxiliary space.
Join the conversation! Your thoughts help the community grow.