Problem Statement

Given two integers L and R. Find the XOR of the elements in the range [L, R].

Examples

Example 1:

Input: L = 3, R = 5
Output: 2

Explanation: (3^4^5) = 2

Example 2:

Input: L = 1, R = 3
Output: 0

Explanation: (1^2^3) = 0

Example 3:

Input: L = 4, R = 10
Output: 11

Explanation: (4^5^6^7^8^9^10) = 11

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A naive approach to solving this will be XOR for every number in the given range.

Approach:

1. A variable can be initiated with 0 that will store the XOR of numbers in given range.
2. Traverse all the numbers in the given range and XOR each number with the variable.
3. Once the traversal is over, the variable stores the result.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    /* Function to find the XOR 
    of numbers from L to R*/
    int findRangeXOR(int l, int r){			
        
        // To store the XOR of numbers
		int ans = 0;
		
		// XOR all the numbers
		for(int i=l; i <= r; i++) {
		    ans ^= i;
		}
		
		// Return the result
		return ans;
	}
};

int main() {
    int l = 3, r = 5;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    XOR of numbers from L to R*/
    int ans = sol.findRangeXOR(l, r);
    
    cout << "The XOR of numbers from " << l << " to " << r << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n) Traversing through all the numbers take O(n) time.
• Space Complexity: O(1) Using only a couple of variables, i.e., constant space.

2️⃣ Optimal Approach (Bit Manipulation)

Intuition:

XORing every number in the given range will be time-consuming and not very efficient.

To solve this problem efficiently, the following observation will come in hand:
The XOR of numbers from 1 to n follows a pattern based on the value of n % 4.

If n % 4 = 0, XOR from 1 to n is n.
If n % 4 = 1, XOR from 1 to n is 1.
If n % 4 = 2, XOR from 1 to n is n+1.
If n % 4 = 3, XOR from 1 to n is 0.

For the required answer, the following line can be used:

XOR(L to R) = XOR(1 to L-1) ^ XOR(1 to R).

Approach:

1. Check the value of n % 4 and return the result based on the identified pattern using a separate function.
2. Use the function to find XOR(1 to L-1) and XOR(1 to R).
3. Return the result of XORing these two values to get the XOR of the range [L, R].

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to find the XOR 
    of numbers from 1 to n*/
    int XORtillN(int n) {
        if(n % 4 == 1) return 1;
        if(n % 4 == 2) return n+1;
        if(n % 4 == 3) return 0;
        return n;
    }
    
public:
    /* Function to find the XOR 
    of numbers from L to R*/
    int findRangeXOR(int l, int r){			
		return XORtillN(l-1) ^ XORtillN(r);
	}
};

int main() {
    int l = 3, r = 5;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    XOR of numbers from L to R*/
    int ans = sol.findRangeXOR(l, r);
    
    cout << "The XOR of numbers from " << l << " to " << r << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(1)
• Space Complexity: O(1)