260. Single Number III
password
URL
type
status
date
slug
summary
tags
category
icon
Single Number III - LeetCode
Can you solve this real interview question? Single Number III - 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. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.   Example 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer. Example 2: Input: nums = [-1,0] Output: [-1,0] Example 3: Input: nums = [0,1] Output: [1,0]   Constraints: * 2 <= nums.length <= 3 * 104 * -231 <= nums[i] <= 231 - 1 * Each integer in nums will appear twice, only two integers will appear once.
Single Number III - LeetCode
https://leetcode.com/problems/single-number-iii/description/
Single Number III - LeetCode

Key point 1

  • a ⊕ a = 0
  • a ⊕ 0 = a
  • a ⊕ b ⊕ a = b
Because a ⊕ a = 0, the pairs of numbers will cancel each other out.
Traverse the array nums and calculate the XOR of all elements. The result will be the XOR of the two numbers that appear only once.
let these single numbers be a and b.
💡
5(101) and 3(011) in this list, the XOR result of list is 6(110).

Key point 2

Because a and b only appear once and a ≠ b, so there must be a bit in the XOR result that is 1.
💡
The XOR result of list is 6(110), this bit is 1 number a is 5(101), this bit is 0 number a is 3(011), this bit is 1
We call the rightmost position with a 1 the rightmost set bit.
To find the rightmost set bit in the XOR result, we can use the two's complement set_bit = xor & -xor. The expression xor & -xor isolates the rightmost set bit in xor. Here, -xor is the two's complement representation of xor.

Key point 3

Traverse the list again, using the rightmost set bit to divide the list. One group has 0 at this position, and the other has 1 at this position. Number a and number b must be divided into different group.
Now, the problem is simplified to ‣. Just calculate the XOR of all elements of tow groups.

Code