Single Number III
Medium · Bit Manipulation · Array · Bit Manipulation
Problem
In the integer array nums, exactly two values appear once and every other value appears exactly twice. Return the two values that appear once, in any order.
Your solution must run in linear time and use only constant extra space.
Examples
Input: nums = [4,1,2,1,2,7] Output: [4,7]
1 and 2 are paired, so 4 and 7 remain. [7,4] is accepted too.
Input: nums = [0,-5] Output: [-5,0]
Both values appear once; either order is accepted.
Constraints
- 2 <= len(nums) <= 3 · 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- Exactly two values appear once; every other value appears exactly twice
Approaches
- Baseline: count with a hash map — time O(n), space O(n)
Follow-up
If every other value appeared three times instead of twice, XOR would no longer cancel them; counting each bit modulo 3 does. And the same split-by-a-differing-bit idea finds a repeated and a missing value in a list that should hold 1..n. Both are the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
