Problem Setter: Ashish Khatkar
Problem Tester : Ayush Shah
Editorialist : Ashish Khatkar
Contest link : XORSN
Practice link : XORSN
XOR and binary representation were well explained in the question, if you need more information visit XOR for XOR and Binary Representation for Binray representation.
You were asked to find the value of 1^2^3^4……………^x for a given value x.
Now, by the property of XOR we can easily formulate that XOR of [1, pow(2,n)-1] is 0. Why ???
Because the way we write binary representation each bit is 1 pow(2,n)/2 times. For example lets write binary representation of 1 to 7 (pow(2,3)-1).
1 => 0 0 1
2 => 0 1 0
3 => 0 1 1
4 => 1 0 0
5 => 1 0 1
6 => 1 1 0
7 => 1 1 1
We can easily see that each bit is 1 pow(2,3)/2 = 4 times. We can extend this to any general n i.e for any pow(2,n) we can generalize this.
Now, ans for this question was simply check if x%4 = {0, 1, 2 or 3}.
If x%4 = 0 ans was x.
If x%4 = 1 ans was 1.
If x%4 = 2 ans was x+1.
If x%4 = 3 ans was 0.
Why take remainder by 4 ???
Because if see binary representation of any 4 consecutive numbers taken in this form 0 to 3, 4 to 7, 8 to 11, 12 to 15 and so on.
Only last 2 bits are changing from 0 0 to 1 1 and rest all bits are same.
For more clarity lets see example of 0 3.
0 => 0 0 XOR = 0
1 => 0 1 XOR = 1 = 1
2 => 1 0 XOR = 1^2 = 3 = x+1
3 => 1 1 XOR = 1^2^3 = 0
So from this we can formulate that when x%4 = 0 ans is x, x%4 = 1 ans is 1, x%4 = 2 ans is x+1 and x%4 = 3 and is 0.
For higher numbers we XOR upto pow(2,n) - 1 which will be 0 which we saw above. For next 4 numbers we can say that only last two bits will change and they change in the way as mentioned above so we get the above formulation.
So, final ans was find the value of x%4, lets say it is a.
If a = 0 ans is x.
else if a = 1 ans is 1.
else if a = 2 ans is x+1.
else if a = 3 ans is 0.