260. Single Number III #

Problem #

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

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

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Problem Summary #

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Note:

• The order of the result is not important. For the example above, [5, 3] is also a correct answer.
• The algorithm is required to run in linear time complexity and not use any extra auxiliary space.

Solution Approach #

• This problem is an enhanced version of Problem 136. In Problem 136, only one number appears once, and all other numbers appear 2 times. This time, there are 2 numbers that appear once, and all other numbers appear 2 times.
• The solution still uses XOR to first eliminate the numbers that appear 2 times. The 2 numbers we need to find must be different, so when the final 2 numbers are XORed, the result must be nonzero. Then which bit should we use as a reference? We can choose any bit; we might as well choose the least significant bit (lsb) that is 1.
• Thus, the entire array will be divided into 2 parts: those whose XOR with lsb is 0 and those whose XOR with lsb is 1. In these 2 parts, use XOR to eliminate all numbers that appear 2 times, and the remaining 2 numbers will be in these 2 parts respectively.

Code #

package leetcode

func singleNumberIII(nums []int) []int {
	diff := 0
	for _, num := range nums {
		diff ^= num
	}
	// Get its last set bit (lsb)
	diff &= -diff
	res := []int{0, 0} // this array stores the two numbers we will return
	for _, num := range nums {
		if (num & diff) == 0 { // the bit is not set
			res[0] ^= num
		} else { // the bit is set
			res[1] ^= num
		}
	}
	return res
}