Leetcode coding challenge notes

Question: Single Number

Given a non-empty 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?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

Notes

Type of question: Number of elements occurrence

The key idea is to use bit operation to solve this kind of question. And here is the knowledge that we need to be familiar with:

  1. XOR of a number with itself is 0
  2. XOR of a number with 0 is the number itself
  3. XOR is commutative so the order of numbers does not matter

In addition,1 & 1 = 1, 0 & 1 = 0, 0 & 0 = 0

Take [2, 2, 3, 3, 4, 5, 5] as an example,

​ 2 XOR 2 = 0; 3 XOR 3 = 0; 5 XOR 5 = 0; output: 4

Take [2, 2, 3, 3, 4, 5, 5, 6] as an example,

​ Similarly, but 4(100) XOR 6(110) = 010(binary), which means the second bit is different between 4 and 6. So we can divide the original array into two subarray by this difference. Then we can just perform XOR operations in two subarrays respectively. The output should be 4, 6