Last Updated: 5 Aug, 2020
Calculate XOR
Easy
Asked in companies
You are given an integer 'N'. For this given integer, find the XOR of all the integers starting from 0 to 'N'.
Input Format :
The first line of input contains the integer 'T' representing the number of test cases.
The next 'T' lines contain an integer 'N' whose XOR is to be calculated.
Output Format :
For each test case/query, print a single line containing a single integer denoting the XOR value of integers from 0 to 'N'.
The output for every test case will be printed in a separate line.
Note:
You are not required to print the output explicitly, it has already been taken care. Return the XOR value against the given input.
Constraints :
1 <= T <= 10 ^ 5
0 <= N <= 10 ^ 9
Time Limit: 1 sec.
Approaches
Before jumping into discussing the approach, it is important to note that if a number is operated with modulo operation say K, then the reminders will always lie in the range 0 ≤ rem < K.
Now, it can be seen that at every multiple of 4, the value of XOR from 1 to that multiple becomes the number itself.
Ex: 4 is the first multiple of 4, hence if we compute 1 ^ 2 ^ 3 ^ 4 = 4
Similarly, for 8, the XOR taken from 1 to 8 will be 8.
Hence, for any positive N, where N is a multiple of 4 then 1 ^ 2 ^ 3 ^ …….. ^ (N - 1) ^ (N) = N
It can further be seen from the binary representation of numbers,1 to N that the value of XOR just before a multiple of 4 is always 0.
We can easily deduce the following, find the remainder of N when it's divided by 4
- If rem = 0, then xor will be equal to n
- If rem = 1, then xor will be equal to 1
- If rem = 2, then xor will be equal to n+1
- If rem = 3 ,then xor will be equal to 0