First we will XOR all the elements from the range [1,n] then using this approach, we have to find xor of elements from the range [1, L – 1] and from the range [1, R] and then xor the respective answers again to get the xor of the elements from the range [L, R]. This is because every element from the range [1, L – 1] will get XORed twice in the result resulting in a 0 which when XORed with the elements of the range [L, R] will give the result.

code:

//XOR elements in range[1,N]

int XOR(int n) {

    int mod = n % 4;

    //if n is a multiple of 4

    if(mod == 0)

    return n;

    //if n%4 gives reaminder 1

    else if(mod == 1)

    return 1;

    //if n%4 gives remainder 2

    else if(mod == 2)

    return n+1;

    //if n%4 gives remainder 3

    else if(mod == 3)

    return 0;

}

int findXOR(int L, int R){

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

}

The idea is based on the following fact.

square(n) = 0 if n == 0 

if n is even     square(n) = 4*square(n/2) 

if n is odd     square(n) = 4*square(floor(n/2)) + 4*floor(n/2) + 1 

Examples :

 square(6) = 4*square(3) = 36

 square(3) = 4*(square(1)) + 4*1 + 1 = 9  

 square(7) = 4*square(3) + 4*3 + 1 = 4*9 + 4*3 + 1 = 49

How does this work? 

If n is even, it can be written as  n = 2*x  n2 = (2*x)2 = 4*x2 

If n is odd, it can be written as  n = 2*x + 1  n2 = (2*x + 1)2 = 4*x2 + 4*x + 1

floor(n/2) can be calculated using a bitwise right shift operator. 

2*x and 4*x can be calculated , below is the implementation based on the above idea. 

code:

#include <bits/stdc++.h> 

int calculateSquare(int num)

{   

    // base case

    if(num == 0)

      return 0;

    // handle negative number

    if(num < 0)

      num = -num;

    //get floor(num/2) using right shift

    int x = num >> 1;

    //if num is odd

    if(num & 1)

      return((calculateSquare(x) << 2) + (x << 2) + 1 );

      //if num is even

    else

      return(calculateSquare(x) << 2);

}

int temp = b;

b = a;

a = temp;