Is there some trick? Because I feel like its trial and error. I saw one question where they asked us to find the missing number in the range of 1 to n, I had no idea how to do it with xor. The solution was to first find the xor of all elements from 1 to n, then the xor of the elements that we were given and then the xor of these both.
How to come to this solution? Because I feel like this solution was found by trial and error. I don't even get how to approach these problems. What do I need to know before solving such problems? Is there some property that I don't know?
The problem can be solved using properties of xor
Properties of xor
xor is Associative
xor is Commutative
X xor X = 0 (X is any number)
X xor 0 = X
For the given problem, Suppose we have to find the missing number in the array [1,2,4,5]
then xor of array = (1^2^4^5)
xor of 1 to 5 = (1^2^3^4^5)
now if you do xor of both, it will be [(1^1)^(2^2)^(4^4)^(5^5)^3]
from the above properties, xor of all pairs will be zero
so we end up with 0^3 = 3
3 is our answer.
it is great to see guys like you taking the bigenners questions seriously not just downvoting the blog or the comments like those people who downvote this blog
In addition to knowing the common properties of XOR, it sometimes helps to think in terms of a single bit at a time (also for AND and OR).
XOR is equivalent to adding the bit representations modulo 2. Therefore it is commutative, associative, and reversible because addition modulo any positive integer n has these properties.