XOR Operation Intuition

Question

I recently came across this question on Leetcode and figured out a solution that I need some clarification with:

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution { public:     int singleNumber(vector<int>& nums) {         int result = 0;         for(auto & c : nums) {             result ^= c;         }         return result;     } }; 

First of all, what sorts of keywords should I be paying attention to in order to figure out that I should be using an XOR operation for this question?

Also, why does XOR'ing all items in the vector with each other give us the one that is not repeated?

---

Thank you all for these responses, here is some more information on bitwise properties for anyone else interested: More bitwise info

Answer 1

1. A ^ 0 == A

2. A ^ A == 0

3. A ^ B == B ^ A

4. (A ^ B) ^ C == A ^ (B ^ C)

(3) and (4) together mean that the order in which numbers are xored doesn't matter.

Which means that, for example, A^B^X^C^B^A^C is equal to A^A ^ B^B ^ C^C ^ X.

Because of the (2) that is equal to 0^0^0^X.

Because of the (1) that is equal to X.

---

I don't think there are any specific keywords that can help you to identify such problems. You just should know above properties of XOR.