Bitwise XOR Property

Segment Trees

One optimized approach leverages the XOR operation’s properties. XORing a number with itself results in zero (a⊕a=0), and XORing zero with any number gives the same number (a⊕0=a). By exploiting these properties, we can XOR consecutive numbers to cancel each other out, leaving only the XOR of the first and last numbers in the range. This method achieves a time complexity of O(1) by finding the XOR of the first L−1 numbers and the first R numbers, then XORing the results to obtain the final answer.

Example: Let’s us consider an example where L=3 and R=6.

The XOR of all numbers from 3 to 6 is calculated as follows:

3⊕4⊕5⊕6=(3⊕4)⊕(5⊕6)
=(7)⊕(3)
=4

Example: To demonstrate computing the bitwise XOR of all numbers in a range using bitwise XOR properties in JavaScript.

JavaScript

function xorRange(L, R) {
    // XOR of numbers from 1 to n
    const xorN = (n) => {
        if (n % 4 === 0) return n;
        if (n % 4 === 1) return 1;
        if (n % 4 === 2) return n + 1;
        return 0;
    };

    // XOR of numbers from 1 to L-1
    const xorLMinusOne = xorN(L - 1);
    // XOR of numbers from 1 to R
    const xorR = xorN(R);

    // XOR of numbers from L to R
    const xorLR = xorLMinusOne ^ xorR;

    return xorLR;
}

const L = 3;
const R = 6;
const result = xorRange(L, R);
console.log(`Bitwise XOR of all numbers from ${L} to ${R} is ${result}`);

Output:

Bitwise XOR of all numbers from 3 to 6 is 4

Time Complexity: O(1), as it does not depend on the size of the range.

Space Complexity: O(1), as we only use a constant amount of additional space regardless of the input size.

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

The complexity of bitwise XOR computation for all the numbers in a specific range is the most frequent difficulty that many people face during the problem-solving process.

Problem Description: Given two integers, L and R, find the bitwise XOR of all numbers in the inclusive range from L to R. There are several approaches to computing the bitwise XOR of all numbers in a range using JavaScript which are as follows:

Table of Content

Bitwise XOR Property
Segment Trees
Binary Indexed Trees (Fenwick Trees)
Bitwise Manipulation

Tags:

#JavaScript #Web Technologies

Segment Trees

Bitwise XOR Property

Compute the Bitwise XOR of all Numbers in a Range using JavaScript

Similar Reads

Contact Us