136. Single Number

Problem

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:

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

Example 2:

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

Problem Summary

Given a non-empty array of integers, every element appears twice except for one element that appears only once. Find the element that appears only once. The algorithm is required to have linear time complexity and use no extra auxiliary space.

Solution Approach

• The problem requires that no auxiliary space be used, and the time complexity can only be linear.
• Why does the problem emphasize that one number appears once and the others appear twice? We think of the property of the XOR operation: any number XORed with itself equals 0. That is to say, if we XOR every number in the array sequentially from beginning to end, the final result is exactly the number that appears only once, because all the numbers that appear twice cancel out in the XOR. Therefore, the final approach is to XOR every number in the array sequentially from beginning to end, and the final result obtained is the XOR result of the two numbers that appear only once. Because all other numbers appear twice, they all cancel out in the XOR. The property used is x^x = 0.

Code

package leetcode

func singleNumber(nums []int) int {
	result := 0
	for i := 0; i < len(nums); i++ {
		result ^= nums[i]
	}
	return result
}