L to R XOR

int calc(int n){

    if(n%4 == 1)return 1;

    else if(n%4 == 2)return n+1;

    else if(n%4 == 3)return 0;

    else return n;

}

int findXOR(int L, int R){

    int n1 = calc(L-1);

    int n2 = calc(R);

    return n1^n2;

}

public class Solution {

    public static int findXOR(int L, int R){

        return (XOR(L-1) ^ XOR(R));

    }

    public static int XOR(int n){

        if(n%4==0) return n;

        if(n%4==1) return 1;

        if(n%4==2) return n+1;

        return 0;

    }

}

int getXOR(int n){

    if(n%4==1) return 1;

   if(n%4==2) return n+1;

   if(n%4==3)return 0;

   if(n%4==0) return n;

}

int findXOR(int L, int R){

    // Write your code here.

   return getXOR(L-1)^getXOR(R);

}

int XorTillN(int N){

    if(N%4==1) return 1;

    else if(N%4==2) return N+1;

     else if(N%4==3) return 0;

    else if(N%4==0) return N;

}

int findXOR(int L, int R){

    // Write your code here.

   return XorTillN(R) ^ XorTillN(L-1);

}

mathematical properties of XOR

• The XOR operation has the property that if you XOR all the numbers from 1 to N, where N is even, the result is a pattern of 0, 1, 0, 1, ... (with the length equal to N/2), and if N is odd, the result is a pattern of N, 1, N+1, 0, ... (with the length equal to N/2 + 1).
• With this property in mind, we can reduce the time complexity of the function from O(N) to O(1) by calculating the XOR of the numbers from 1 to L-1 and from 1 to R, and then XORing these two results.
• TIME COMPLEXITY :O(1)

Approach:

Xor of number from 1 to a will be

Xor    a

0 if a%4==0

1 if a%4==1

a+1 if a%4==2

0  if a%4==3 

.

.

.

Java  Code: 

public class Solution {

    public static int findXOR(int L, int R){

        int a=L%4;

        if(a==0){a=L;}

        else if(a==1){a=1;}

        else if(a==2){a=L+1;}

        else if(a==3){a=0;}

        int b=R%4;

        if(b==0){b=R;}

        else if(b==1){b=1;}

        else if(b==2){b=R+1;}

        else{b=0;}

        return (a^b)^L;

    }

}

int helper(int n)
{
    int mod=n%4;
    switch(mod)
    {
        case 0: return n;
        case 1: return 1;
        case 2: return n+1;
        case 3: return 0;
    }
}
int findXOR(int L, int R){
    // Write your code here.
    return helper(L-1)^helper(R);
}

int findXOR(int L, int R){

    // Write your code here.

    int ans=L;

    for(int i=L+1;i<=R;i++){

        ans=ans^i;

    }

    return ans;

}

int XOR(int n)
{
    if(n%4==0)return n;
    if(n%4==1)return 1;
    if(n%4==2)return n+1;
    if(n%4==3)return 0;
}

int findXOR(int L, int R){
    int ans = XOR(R)^XOR(L-1);
    return ans;
}

//We observe a pattern from 1->n when modulus with 4
// N = 1                        1 <-| 1%4 = 1 -> 1 
// N = 2        1^2             3   | 2%4 = 2 -> 2+1
// N = 3        3^3             0   | 3%4 = 3 -> 0
// N = 4        4^0             4 <-| 4%4 = 0 -> 4
// N = 5        5^4             1 <-| 5%4 = 1 -> 1
// N = 6        5^6             7   | 6%4 = 2 -> 6+1
// N = 7        7^7             0   | 7%4 = 3 -> 0
// N = 8        8^0             8 <-| 8%4 = 0 -> 8

// for L=3 and R = 5
// XOR(R)^XOR(L-1) = (1^2^3^4^5)^(1^3) => (3^4^5) =>ANS

int makeXor(int n){

    if(n%4 == 0){

       return n;

    }

    if(n%4 == 1){

        return 1;

    }

    if(n%4 == 2){

        return n+1;

    }

    if(n%4 == 3){

        return 0;

    }

}

int findXOR(int L, int R){

    int ans = makeXor(R) ^ makeXor(L-1);

    return ans;

}