Optimal Exor Of Range In O(1) Time Complexity
Optimal solution for finding XOR of range 1 to N: use N%4 to determine result in O(1) time complexity. For ranges L-R, find XOR of L-1 and R separately and XOR the results.
Given an integer number N, find the exor of the range 1 to N
exor of 1 ^ 2 ^ 3 ^4 ^.....N;
Brute force approach:
Tc:O(n)
Sc:O(1)
public int findExor(int N){
//naive/brute force approach:
int val = 0;
for(int i=1;i<5;i++){
val = val^ i;
}
return val;
}
Optimal approach:
Tc:O(1)
Sc:O(1)
public int getExor(int N){
//better approach
/**
* one thing to observe is
* 1 = 001 = 1
* 1 ^2 = 001 ^ 010 = 011= 3
* 1^2^3 = 011 ^ 011 = 0= 0
*...