💬 Discord
Sign In
NeetCode #850LC-136EasyBit ManipulationNC 150NC 250
← Back to All Problems

#850 · #136 · Single Number(只出现一次的数字)

📌 Problem Statement & Constraints

Every element of the array nums appears exactly twice except for one element that appears once. Return that single element. Constraints: 1 <= nums.length <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4. Linear time and constant extra space are required.

💡 Core Algorithmic Approaches

  1. XOR has the identities x ^ x = 0 and x ^ 0 = x, and it is commutative and associative.
  2. XOR-ing the whole array therefore pairs up every duplicate and annihilates it, leaving only the lonely element.
  3. The order of operations does not matter, so a single left-to-right pass suffices.
  4. This beats the hash-set approach because it needs no extra memory and beats sorting because it stays linear.

💻 Benchmark Python3 Implementation

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for x in nums:
            res ^= x                    # duplicate pairs cancel to zero
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the array.
💾 Space Complexity
O(1): a single accumulator.

⚠️ Interview Pitfalls & Follow-ups

  • Using a hash set or a counter: O(n) extra space for no reason when XOR achieves O(1).
  • Sorting then scanning for the unpaired value: O(n log n) and mutates the input.
  • Assuming the trick extends to three copies: that is 137 Single Number II and needs bit counting or a state machine.
  • Starting the accumulator from nums[0]: it must start at 0, or the first element is counted twice.