Given two integers L
and R
, compute the XOR of all numbers in the inclusive range [L, R]
.
That is, return the result of: L ^ (L+1) ^ (L+2) ^ ... ^ R
The goal is to perform this efficiently without looping through every number.
#include <stdio.h>
int xorFrom0To(int n) {
switch (n % 4) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
}
return 0; // should never reach here
}
int xorRange(int L, int R) {
return xorFrom0To(R) ^ xorFrom0To(L - 1);
}
int main() {
int L = 3, R = 9;
int result = xorRange(L, R);
printf("XOR from %d to %d is %d\n", L, R, result);
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The algorithm uses a mathematical pattern to directly compute the XOR from 0 to L-1 and from 0 to R, both in constant time. There are no loops or recursive calls involved. |
Average Case | O(1) | Regardless of the size of the range [L, R], the XOR is computed using two constant-time operations: xorFrom0To(R) and xorFrom0To(L - 1). |
Worst Case | O(1) | Even when the range [L, R] is very large, the algorithm does not iterate over the numbers. It leverages a modulo-4 pattern for constant-time calculation. |
Comments
Loading comments...