NeetCode #852LC-260MediumBit Manipulation
← Back to All Problems#852 · #260 · Single Number III(只出现一次的数字 III)
📌 Problem Statement & Constraints
Every element of the array
nums appears exactly twice except for two elements that each appear once. Return those two unique elements in any order. Constraints: 2 <= nums.length <= 3 * 10^4, -2^31 <= nums[i] <= 2^31 - 1. Linear time and constant extra space are required.💡 Core Algorithmic Approaches
- XOR-ing the whole array cancels every duplicate pair and leaves
x ^ y, the XOR of the two unique values. - That value is non-zero (the two values differ), so pick any set bit of it -- the lowest set bit is convenient.
- The two unique values must differ at that bit, so partition the array into two groups by whether that bit is set.
- XOR-ing each group separately cancels the duplicates and isolates one unique value per group.
💻 Benchmark Python3 Implementation
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor_all = 0
for x in nums:
xor_all ^= x # equals x ^ y for the two singles
low = xor_all & (-xor_all) # a bit where the two singles differ
a = 0
for x in nums:
if x & low: # partition by that distinguishing bit
a ^= x
return [a, xor_all ^ a]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two passes.
💾 Space Complexity
O(1): two accumulators.
⚠️ Interview Pitfalls & Follow-ups
- Trying to extend the single-XOR trick directly: XOR of the whole array gives
x ^ y, notxory. - Choosing a bit that is zero in
xor_all: the distinguishing bit must be set inxor_all, otherwise the partition is meaningless. - Returning the XOR of a group twice: the second value is
xor_all ^ a, sincexor_all == a ^ b. - Using a hash map: it solves the problem but uses O(n) space, which the constant-space requirement forbids.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.