Bit Manipulation

LeetCode 136

LeetCode #136Difficulty: EasyNeetCode 150

LeetCode 136: Single Number

LeetCode

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Problem Description

Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Examples:
Input: nums = [4,1,2,1,2]
Output: 4
Constraints:
  • 1 <= nums.length <= 3 * 10^4
  • Every element appears twice except for one.

Core Mental Model

XOR (^) has two crucial properties: 1. Self-inverse: x ^ x = 0. 2. Identity: x ^ 0 = x. XORing all elements together cancels every paired duplicate to 0, leaving only the unique element!

Formal Loop Invariant

Invariant: Accumulator holds running XOR sum; duplicate bit patterns cancel out to 0.

Key Architectural Takeaway:

Bitwise XOR eliminates duplicate pairs without requiring a hash set.

Asymptotic Complexity Analysis

Time ComplexityO(N) single passLinear scan
Space ComplexityO(1) scalar register.Constant auxiliary

Bottleneck: Single bitwise XOR loop.

Edge Cases & Screener Traps

  • Single element array [1]