Calculate XOR

Easy
0/40
Average time to solve is 23m
profile
Contributed by
17 upvotes
Asked in companies
SamsungNokia

Problem statement

You are given an integer 'N'. For this given integer, find the XOR of all the integers starting from 0 to 'N'.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3
0
2
3
Sample Output 1 :
0
3
0
Explanation for Sample Input 1:
In the first test, the only number is there, so the answer is 0.

In the second test, We are getting the xor of 0 to 2 as 0 xor 1 xor 2, which equals 3.

In the third test, We are getting the xor of 0 to 3 as 0 xor 1 xor 2 xor 3, which equals 0.
Sample Input 2:
2
10
12
Sample Output 2 :
11
12
Hint

Is there any pattern in the xor's we are getting?

Approaches (1)
Mathematical Approach

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
Time Complexity

O(1).

 

Simple constant operations, hence constant time is needed.

Space Complexity

O(1).

 

No extra space is used.

Code Solution
(100% EXP penalty)
Calculate XOR
Full screen
Console