Find XOR of numbers from L to R | Optimal Solution using Bit Manipulation

You are given two integers L and R, your task is to find the XOR of elements of the range [L, R].

Here’s the [Problem Link] to begin with.

Example:

Input: 
L = 4, R = 8 
Output:
8 
Explanation:
4 ^ 5 ^ 6 ^ 7 ^ 8 = 8

Your Task:

Your task is to complete the function findXOR() which takes two integers l and r and returns the XOR of numbers from l to r.

Expected Time Complexity: O(1).
Expected Auxiliary Space: O(1).

Constraints:

• 1<=l<=r<=10⁹

Solution 1: Brute Force Approach (Loop and XOR)

Intuition

This is the straightforward way, like adding up numbers one by one! Start with a result of 0, then loop from L to R, XORing each number into the result. It’s simple, but for large R – L (up to 10^9), it would be too slow because looping billions of times isn’t efficient.

Detailed Approach

1. Initialize Result: Set ans = 0.
2. Loop from L to R: For each number i, do ans = ans ^ i.
3. Return the Result: After the loop, ans is the XOR from L to R.

Code

class Solution:
    def findXOR(self, l, r):
        ans = 0  # Initialize result
        
        # Loop through each number and XOR
        for i in range(l, r + 1):
            ans = ans ^ i  # XOR current number
        
        return ans

Code Explanation

We start with ans as 0 (XOR identity). Then, for every number from l to r, we XOR it with ans. This builds up the total XOR step by step. It’s correct but not optimal for large ranges because the loop runs (r – l + 1) times.

Dry Run

Let’s trace through: L=1, R=3

Step-by-Step:

• ans=0
• i=1: ans=0 ^ 1 = 1
• i=2: ans=1 ^ 2 = 3
• i=3: ans=3 ^ 3 = 0

Result: 0

Time and Space Complexity

• Time Complexity: O(r – l + 1) – Worst case O(10^9) for large ranges, which is too slow.
• Space Complexity: O(1) – No extra space needed.

Simplifying It

This is like manually adding scores in a game one by one. It works for small games (small ranges), but for a huge tournament (large R – L), you’d be there forever. We need a smarter way!

Solution 2: Optimal Approach (XOR Pattern)

Intuition

XOR has a cool repeating pattern every 4 numbers! If you compute XOR from 1 to N, it depends on N % 4:

• If N % 4 == 0: XOR = N
• If N % 4 == 1: XOR = 1
• If N % 4 == 2: XOR = N + 1
• If N % 4 == 3: XOR = 0

To get XOR from L to R, it’s XOR(1 to R) ^ XOR(1 to L-1). This way, we cancel out the part before L and get exactly what we need in constant time!

Detailed Approach

1. Helper Function: Create XORfrom1ToN(num) that returns XOR from 1 to num based on num % 4.
2. Edge Case: If num < 0, XOR is 0 (for L=1, XOR(1 to L-1)=0).
3. Compute Result: Return XORfrom1ToN(r) ^ XORfrom1ToN(l – 1).
4. Why It Works: XOR is associative and commutative, and A ^ B ^ C ^ … ^ Z = (1 to Z) ^ (1 to (A-1)).

Code

class Solution:
    # Helper function to compute XOR from 1 to num
    def XORfrom1ToN(self, num):
        if num < 0:
            return 0  # XOR from 1 to 0 or negative is 0
        if num % 4 == 1:
            return 1
        elif num % 4 == 2:
            return num + 1
        elif num % 4 == 3:
            return 0
        else:
            return num
    
    # Main function to compute XOR from l to r
    def findXOR(self, l, r):
        # XOR(L to R) = XOR(1 to R) ^ XOR(1 to L-1)
        return self.XORfrom1ToN(l - 1) ^ self.XORfrom1ToN(r)

Code Explanation

The XORfrom1ToN function uses the pattern of XOR prefixes. For example, XOR(1 to 4) = 4, XOR(1 to 5) = 1, and so on. By computing the prefix XOR up to R and up to L-1, their XOR gives exactly the XOR from L to R because the parts before L cancel out (A ^ B = C means A ^ C = B). This is super fast – no loops needed!

Dry Run

Let’s trace through: L=4, R=7

Step 1: XORfrom1ToN(3) (L-1=3)

• 3 % 4 = 3 → return 0

Step 2: XORfrom1ToN(7)

• 7 % 4 = 3 → return 0

Step 3: 0 ^ 0 = 0

Wait, but actual XOR(4^5^6^7) = 4^5=1, 1^6=7, 7^7=0? Wait, let’s calculate:

• 4=100, 5=101 → 4^5=001 (1)
• 6=110 → 1^6=111 (7)
• 7=111 → 7^7=000 (0)

But according to pattern:

• XOR(1 to 3)=1^2^3=0
• XOR(1 to 7)=1^2^3^4^5^6^7
  Let’s verify the pattern:
  Actual XOR(1 to 7):
  1^2=3, 3^3=0, 0^4=4, 4^5=1, 1^6=7, 7^7=0
  Yes, 7%4=3 → 0, correct.

But actual 4^5^6^7:
Let’s calculate: 4^5=1, 1^6=7, 7^7=0
But 0 ^ 0 = 0, matches!

Another example: L=1, R=3

• XOR(1 to 0)=0
• XOR(1 to 3)=0 (3%4=3→0)
• 0 ^ 0 = 0, and 1^2^3=0, correct.

One more: L=2, R=4

• XOR(1 to 1)=1 (1%4=1→1)
• XOR(1 to 4)=4 (4%4=0→4)
• 1 ^ 4 = 5
  Actual: 2^3^4 = 2^3=1, 1^4=5, correct!

Time and Space Complexity

• Time Complexity: O(1) – Constant time, no loops!
• Space Complexity: O(1) – No extra space needed.

Simplifying It

This is like knowing a secret formula for summing numbers quickly instead of adding one by one. The pattern repeats every 4 numbers, so we can jump straight to the answer. For L to R, it’s like subtracting the XOR up to L-1 from the XOR up to R using XOR properties. Genius for large ranges!

Summary

The optimal pattern approach is preferred because it runs in constant time, perfect for constraints like L and R up to 10^9. The brute force is easy to understand but too slow for big inputs.

This problem shows the beauty of bitwise patterns, once you learn the cycle every 4 numbers, you can solve it instantly! Practice with small ranges to verify the pattern. If you have questions, drop them below. Happy coding! 🚀

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.