XOR of numbers in a given range

Intuition:

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

Approach:

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

Dry Run:

Solution:

#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;
}
class Solution {

    /* Function to find the XOR 
    of numbers from L to R */
    public 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;
    }

    public static void main(String[] args) {
        int l = 3, r = 5;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to get the
        XOR of numbers from L to R */
        int ans = sol.findRangeXOR(l, r);
        
        System.out.println("The XOR of numbers from " + l + " to " + r + " is: " + ans);
    }
}
class Solution:
    
    # Function to find the XOR 
    # of numbers from L to R
    def findRangeXOR(self, l, r):
        
        # To store the XOR of numbers
        ans = 0
        
        # XOR all the numbers
        for i in range(l, r + 1):
            ans ^= i
        
        # Return the result
        return ans

if __name__ == "__main__":
    l, r = 3, 5
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to get the
    # XOR of numbers from L to R
    ans = sol.findRangeXOR(l, r)
    
    print(f"The XOR of numbers from {l} to {r} is: {ans}")
class Solution {
    
    /* Function to find the XOR 
    of numbers from L to R */
    findRangeXOR(l, r) {
        
        // To store the XOR of numbers
        let ans = 0;
        
        // XOR all the numbers
        for (let i = l; i <= r; i++) {
            ans ^= i;
        }
        
        // Return the result
        return ans;
    }
}

const main = () => {
    const l = 3, r = 5;
    
    /* Creating an instance of 
    Solution class */
    const sol = new Solution();
    
    /* Function call to get the
    XOR of numbers from L to R */
    const ans = sol.findRangeXOR(l, r);
    
    console.log(`The XOR of numbers from ${l} to ${r} is: ${ans}`);
};

main();

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.

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:

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

Dry Run:

Solution:

#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;
}
import java.util.*;

class Solution {
    /* Function to find the XOR 
    of numbers from 1 to n */
    private 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;
    }
    
    /* Function to find the XOR 
    of numbers from L to R */
    public int findRangeXOR(int l, int r) {
        return XORtillN(l - 1) ^ XORtillN(r);
    }
    
    public static void main(String[] args) {
        int l = 3, r = 5;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to get the
        XOR of numbers from L to R */
        int ans = sol.findRangeXOR(l, r);
        
        System.out.println("The XOR of numbers from " + l + " to " + r + " is: " + ans);
    }
}
class Solution:
    # Function to find the XOR 
    # of numbers from 1 to n
    def XORtillN(self, n):
        if n % 4 == 1:
            return 1
        if n % 4 == 2:
            return n + 1
        if n % 4 == 3:
            return 0
        return n

    # Function to find the XOR 
    # of numbers from L to R 
    def findRangeXOR(self, l, r):
        return self.XORtillN(l - 1) ^ self.XORtillN(r)

if __name__ == "__main__":
    l, r = 3, 5
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to get the
    # XOR of numbers from L to R
    ans = sol.findRangeXOR(l, r)
    
    print(f"The XOR of numbers from {l} to {r} is: {ans}")
class Solution {
    /* Function to find the XOR 
    of numbers from 1 to n */
    XORtillN(n) {
        if (n % 4 === 1) return 1;
        if (n % 4 === 2) return n + 1;
        if (n % 4 === 3) return 0;
        return n;
    }
    
    /* Function to find the XOR 
    of numbers from L to R */
    findRangeXOR(l, r) {
        return this.XORtillN(l - 1) ^ this.XORtillN(r);
    }
}

const l = 3, r = 5;

/* Creating an instance of 
Solution class */
const sol = new Solution();

/* Function call to get the
XOR of numbers from L to R */
const ans = sol.findRangeXOR(l, r);

console.log(`The XOR of numbers from ${l} to ${r} is: ${ans}`);

Complexity Analysis:

Time Complexity: O(1) Using constant time operations.

Space Complexity: O(1) Using a couple of variables i.e., constant space.

Problem List

XOR of numbers in a given range

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code