Single Number

Difficulty: Easy
Topics: Array, Bit Manipulation
Link: https://leetcode.com/problems/single-number/

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.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once.

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem
1. Technical Definition:
  Given an array nums of length n (where n is guaranteed to be odd due to the problem’s structure), each integer in nums appears exactly twice except for one distinct integer that appears exactly once. Formally, let ( S ) be the multiset of elements from nums. Define the frequency function ( f: S \to \mathbb{N} ) where ( f(x) ) counts occurrences of ( x ) in ( S ). Then: [ \exists! a \in S \text{ such that } f(a) = 1, \quad \forall x \in S \setminus {a}, f(x) = 2. ] The objective is to compute ( a ) with ( O(n) ) time complexity and ( O(1) ) auxiliary space complexity (i.e., using only a constant number of extra variables beyond the input).
2. Beginner-Friendly Explanation:
  Imagine you have a bag full of paired identical marbles, but one marble is different and has no duplicate. You want to find that unique marble by only looking at the marbles one by one, without using any extra containers to sort them. You need a method that works quickly even if there are thousands of marbles, and you can only use a tiny notepad to jot down a single number while you examine them.
3. Mathematical Reformulation:
  Let ( \oplus ) denote the bitwise XOR operation (exclusive OR). For any integer ( x ), ( x \oplus x = 0 ) and ( x \oplus 0 = x ). Given the array ( [x_1, x_2, \dots, x_n] ), the single number ( a ) satisfies: [ a = \bigoplus_{i=1}^n x_i ] because XOR is commutative and associative, so all pairs cancel out (( x \oplus x = 0 )), and the XOR of all zeros is zero, leaving ( 0 \oplus a = a ). This identity provides an efficient solution.
Constraint Analysis
- 1 <= nums.length <= 3 * 10^4:
  - Limitation on Time: The upper bound of 30,000 elements rules out quadratic algorithms (e.g., double nested loops), which would take up to ( 9 \times 10^8 ) operations—borderline for modern CPUs but likely too slow under typical time limits. Linear-time algorithms (( \approx 3 \times 10^4 ) ops) are safe.
  - Hidden Edge Cases: The lower bound of 1 ensures the array is never empty, so we don’t need to handle a null or empty input. Additionally, the length is odd, which is invariant under the problem’s frequency condition (since ( 2k + 1 ) total elements). This oddness can be exploited in approaches like sorting and pairwise comparison.
- -3 * 10^4 <= nums[i] <= 3 * 10^4:
  - Range Implications: The values fit within a 16-bit signed integer range (actually up to 30,000, so 15 bits plus sign). This limited range might suggest a bucket-counting solution using an array of size 60,001, which uses ( O(\text{range}) ) space. While constant for fixed bounds, it is memory-inefficient compared to the bitwise XOR method. Moreover, negative numbers require careful handling in bitwise operations (two’s complement representation), but XOR works identically on negative integers because it operates on raw bits.
- Each element appears twice except for one:
  - Core Property: This symmetry is the key to cancellation techniques. It also implies that if we sort the array, the single element will break the pairwise adjacency pattern. However, sorting would require ( O(n \log n) ) time, violating the linear runtime requirement unless we use a non-comparison sort (like counting sort), which would then violate constant extra space if we allocate a count array proportional to the range.

2. Intuition Scaffolding

Generate 3 Analogies
1. Real-World Metaphor (Sock Pairing):
  You have a laundry basket with many socks, each sock has an identical twin except one lone sock. Without using additional baskets or labels, you can use a “magic marker” that marks socks in such a way that marking the same sock twice erases the mark. As you pull each sock from the basket, you apply the marker. At the end, the only sock retaining a mark is the unmatched one. XOR acts as this marker: each number is “marked” by XOR-ing with a running value, and duplicate marks cancel.
2. Gaming Analogy (Team Formation):
  In an online game, players enter a lobby and must form teams of two. Each player has a unique ID, but due to a bug, one player is left without a partner. To identify them, the game server could ask each player to broadcast their ID, and if the same ID is broadcast twice, it’s removed from the list. The only ID remaining is the unpaired player. This broadcast-and-cancel mimics the XOR accumulation.
3. Mathematical Analogy (Group Theory):
  Consider the set of integers under the XOR operation. This forms an abelian group where every element is its own inverse (i.e., ( x \oplus x = 0 )). The problem reduces to computing the “sum” (XOR) of all elements in the group. Since the group is associative and commutative, the sum of all paired elements is the identity element 0, so the overall sum equals the single element.
Common Pitfalls Section
1. Assuming Global Min/Max Helps:
  The unique element is not necessarily the minimum or maximum; it could be anywhere in the range. Example: [1,2,2] has unique 1 (min), but [1,1,2] has unique 2 (max). So extremal properties cannot isolate it.
2. Using Summation Without Duplication Awareness:
  Calculating 2 * sum(set(nums)) - sum(nums) requires storing the set, which uses ( O(n) ) space. Even if we could compute the set sum without storage, the formula relies on the exact duplicate count being two, which holds, but obtaining the set implicitly uses extra memory.
3. Hash Table Overhead:
  While a hash table (dictionary) provides ( O(1) ) average insertion/lookup, it allocates memory proportional to the number of distinct keys, which is roughly ( \lfloor n/2 \rfloor + 1 ), i.e., ( O(n) ) space. This violates the constant extra space constraint.
4. Sorting’s Time Trade-off:
  Sorting the array in-place (e.g., with quicksort) uses ( O(1) ) extra space but takes ( O(n \log n) ) time. For ( n = 30,000 ), ( n \log n \approx 30,000 \times 15 \approx 450,000 ) operations, which might be acceptable in practice but fails the strict linear runtime requirement.
5. Bitwise XOR Misapplication:
  XOR works only because duplicates appear exactly twice. If an element appeared three times, XOR would leave that element’s value (since ( x \oplus x \oplus x = x )), breaking the solution. The problem guarantees exactly two occurrences, but one must verify this assumption.

3. Approach Encyclopedia

Approach 1: Brute Force (Double Loop)

Pseudocode:

def singleNumber(nums):
    n = len(nums)
    for i in range(n):
        is_single = True
        for j in range(n):
            if i != j and nums[i] == nums[j]:
                is_single = False
                break
        if is_single:
            return nums[i]

Complexity Proof:
- Time: Outer loop runs ( n ) times. Inner loop runs up to ( n ) times per outer iteration, giving worst-case ( \sum_{i=1}^n n = n^2 ) comparisons. Hence, ( O(n^2) ).
- Space: Only uses a few integer variables (i, j, is_single), so ( O(1) ) extra space.

Visualization:

nums = [4, 1, 2, 1, 2]
i=0 → check j=1,2,3,4: 4 not found → return 4.
But worst-case (single at end):
nums = [1,1,2,2,4]
i=0 → find duplicate at j=1.
i=1 → duplicate at j=0.
i=2 → duplicate at j=3.
i=3 → duplicate at j=2.
i=4 → no duplicate → return 4.

Approach 2: Sorting & Linear Scan

Pseudocode:

def singleNumber(nums):
    nums.sort()               # In-place sort, O(1) space if heapsort, but Python's sort is O(n) space.
    n = len(nums)
    i = 0
    while i < n - 1:
        if nums[i] != nums[i+1]:
            return nums[i]
        i += 2
    return nums[-1]           # Last element is single if not found earlier

Complexity Proof:
- Time: Sorting dominates: ( O(n \log n) ) for comparison sorts. The subsequent scan is ( O(n) ).
- Space: Depending on sorting algorithm: Python’s sort() uses Timsort, which requires ( O(n) ) space in worst case. In-place heapsort would be ( O(1) ), but not guaranteed.

Visualization:

nums = [4,1,2,1,2] → sorted → [1,1,2,2,4]
Compare pairs:
  (1,1) equal → skip.
  (2,2) equal → skip.
  leftover 4 → return 4.

Approach 3: Hash Table Frequency Count

Pseudocode:

from collections import defaultdict
def singleNumber(nums):
    freq = defaultdict(int)
    for num in nums:
        freq[num] += 1
    for num, count in freq.items():
        if count == 1:
            return num

Complexity Proof:
- Time: Two passes: first pass ( O(n) ) for building hash table, second pass ( O(k) ) where ( k ) is number of distinct keys, at most ( \lfloor n/2 \rfloor + 1 ), so overall ( O(n) ).
- Space: Hash table stores counts for each distinct number, so ( O(k) = O(n) ) extra space.

Approach 4: Mathematical Set Sum

Pseudocode:

def singleNumber(nums):
    return 2 * sum(set(nums)) - sum(nums)

Complexity Proof:
- Time: set(nums) iterates over nums to build the set: ( O(n) ). sum(set(nums)) sums distinct elements: ( O(k) ). sum(nums) sums all: ( O(n) ). Total ( O(n) ).
- Space: The set stores distinct elements: ( O(k) = O(n) ).

Approach 5: Bit Manipulation (XOR) – Optimal

Pseudocode:

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Complexity Proof:
- Time: Single loop over ( n ) elements, each XOR operation is ( O(1) ), so total ( O(n) ).
- Space: One integer variable result, plus loop variable, so ( O(1) ) extra space.

Visualization:

nums: [4, 1, 2, 1, 2]
Binary representation (simplified 4-bit):
  4: 0100
  1: 0001
  2: 0010
  1: 0001
  2: 0010

Step-by-step XOR:
  result = 0000 (0)
  ^ 0100 (4) → 0100 (4)
  ^ 0001 (1) → 0101 (5)
  ^ 0010 (2) → 0111 (7)
  ^ 0001 (1) → 0110 (6)
  ^ 0010 (2) → 0100 (4)   → returns 4.

4. Code Deep Dive

Line-by-Line Annotations (Optimal XOR Solution)

def singleNumber(nums):
    result = 0               # Initializing to 0 because 0 is the identity for XOR: 0 ^ x = x.
    for num in nums:        # Iterate once through the entire array. Each element is visited exactly once.
        result ^= num       # Accumulate XOR. Duplicate numbers cancel because x ^ x = 0.
    return result           # After loop, result holds the single number.

Edge Case Handling
- Example 1 ([2,2,1]):
  - result starts 0.
  - First iteration: result = 0 ^ 2 = 2.
  - Second: result = 2 ^ 2 = 0.
  - Third: result = 0 ^ 1 = 1. Returns 1.
- Example 2 ([4,1,2,1,2]): As visualized above, returns 4.
- Example 3 ([1]):
  - Single element: result = 0 ^ 1 = 1. Returns 1.
- Large Input (30,000 elements): The loop runs efficiently without memory overhead.
- Negative Numbers: XOR works on two’s complement representation. For example, -1 is all bits set, and -1 ^ -1 = 0. The cancellation property holds.

5. Complexity War Room

Hardware-Aware Analysis
- Time: For ( n = 3 \times 10^4 ), the XOR loop performs 30,000 operations. Each XOR is a single CPU instruction on modern processors, taking roughly 0.3–1 nanosecond per operation (depending on clock speed). Total execution time is under 0.1 ms, well within limits.
- Memory: The algorithm uses one additional 32-bit integer (4 bytes). The input array is read sequentially, which is cache-optimized: 30,000 integers occupy about 120 KB (assuming 4-byte ints), fitting comfortably in L2/L3 cache. Thus, memory accesses are fast.
- Energy Efficiency: XOR is a bitwise operation that consumes minimal power compared to multiplication or branching, making this solution energy-efficient for embedded systems.

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability (1–10)	Interview Viability
Brute Force	( O(n^2) )	( O(1) )	9 (simple logic)	❌ Fails due to time
Sorting & Scan	( O(n \log n) )	( O(1) ) or ( O(n) )	8 (clear pattern)	⚠️ Acceptable if XOR not required
Hash Table	( O(n) )	( O(n) )	9 (intuitive)	⚠️ Good but not constant space
Mathematical Set Sum	( O(n) )	( O(n) )	8 (clever math)	⚠️ Same as hash table
XOR (Optimal)	( O(n) )	( O(1) )	7 (requires bitwise knowledge)	✅ Best – meets all constraints

6. Pro Mode Extras

Variants Section
1. Single Number II (LeetCode 137):
  - Problem: Every element appears three times except one. Find it.
  - Solution: Use bit counting: for each bit position, count the number of 1s across all numbers modulo 3. The leftover bits form the single number.
2. Single Number III (LeetCode 260):
  - Problem: Two elements appear once, others twice. Find both.
  - Solution: XOR all numbers to get xor_all = a ^ b. Find any set bit in xor_all (e.g., the rightmost 1). Partition numbers into two groups based on that bit, then XOR each group separately to get a and b.
3. Single Number with Sorted Input:
  - If the array is already sorted, we can use binary search in ( O(\log n) ) time: the single element will be at the first even index where nums[i] != nums[i+1].
4. Single Number with Pairs but Not Necessarily Adjacent:
  - XOR still works regardless of order because XOR is commutative.
5. Single Number in a Stream:
  - If numbers arrive in a stream (too large to store), XOR can be computed on-the-fly with constant memory.
Interview Cheat Sheet
- First Mention: Always state the time and space constraints upfront. For this problem, highlight “linear time, constant space” as the key challenge.
- Fallback Strategy: If you don’t recall XOR, propose sorting or hash table, then discuss trade-offs. The interviewer may hint towards bit manipulation.
- Bitwise Tricks: Memorize: x ^ x = 0, x ^ 0 = x, x ^ y = y ^ x, and (x ^ y) ^ z = x ^ (y ^ z).
- Testing: Provide test cases:
  - All positive numbers.
  - Mix of negative and positive.
  - Single element array.
  - Large even-length array (but note: length must be odd by problem statement).
- Follow-up Questions: Be prepared for “What if duplicates appear three times?” or “What if two numbers appear once?”

#136 - Single Number

Single Number

Problem Description

Solution

1. Problem Deconstruction (500+ words)

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras