⚡Flashcard Drill➔
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

  1. XOR-ing the whole array cancels every duplicate pair and leaves x ^ y, the XOR of the two unique values.
  2. That value is non-zero (the two values differ), so pick any set bit of it -- the lowest set bit is convenient.
  3. The two unique values must differ at that bit, so partition the array into two groups by whether that bit is set.
  4. 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, not x or y.
  • Choosing a bit that is zero in xor_all: the distinguishing bit must be set in xor_all, otherwise the partition is meaningless.
  • Returning the XOR of a group twice: the second value is xor_all ^ a, since xor_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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems