How do you solve Single Number?

Initialize a result variable to zero. Iterate through the array, XORing each element with the result. After processing all elements, the result holds the unique number. This approach runs in O(n) time and O(1) auxiliary space.

Single Number

Q: What is the time complexity of Single Number?

O(n). The algorithm iterates through the array once, performing a constant-time XOR operation per element.

Q: What pattern does Single Number use?

The Pattern: Bitwise XOR (Pair Cancellation) The Heuristic: XORing a number with itself cancels to zero, and XORing zero with a number yields the number; thus, XORing all elements in an array where every element except one appears twice isolates the unique element in a single pass with constant space.

Easy Bitwise XOR

Problem

Given a non-empty array of integers nums where every element appears twice except for one, return the single element that appears only once.

1 ≤ nums.length ≤ 3 * 10⁴
−3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴
Each element appears twice except for one element which appears only once.

Example

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

Output: 4

The brute-force approach would count occurrences of each number, which requires extra space or multiple passes. Instead, the algorithm uses the XOR operation's properties. XORing a number with itself yields zero, and XORing zero with a number yields the number itself. Iterating through the array and XORing all elements cancels out all duplicates, leaving only the unique element. For example, starting with res = 0, XOR with 4 gives 4, then XOR with 1 gives 5, XOR with 2 gives 7, XOR with 1 cancels the previous 1 resulting in 6, XOR with 2 cancels the previous 2 resulting in 4, which is the unique element.

Approach

Straightforward Solution

A naive approach uses a hash map or dictionary to count occurrences of each number, then iterates to find the one with count one. This requires O(n) time and O(n) space, which is suboptimal in space.

Core Observation

The XOR operation has two critical properties: it is commutative and associative, and any number XORed with itself is zero. This means XORing all elements in the array cancels out all duplicates, leaving only the unique element.

Path to Optimal

Preview

Recognizing the XOR properties allows a linear time and constant space solution. By XORing all elements, duplicates cancel out…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a result variable to zero. Iterate through the array, XORing each element with the result…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once, performing a constant-time XOR operation per element.

Space

O(1)

Only a single variable is used to accumulate the XOR results, requiring constant auxiliary space regardless of input size.

Pattern Spotlight

Bitwise XOR (Pair Cancellation)

XORing a number with itself cancels to zero, and XORing zero with a number yields the number; thus, XORing all elements in an array where every element except one appears twice isolates the unique element in a single pass with constant space.

Solution

Python

1class Solution:
  def singleNumber(self, nums: list[int]) -> int:
      res = 0
      for n in nums:
          res = n ^ res
      return res

Step-by-Step Solution

Initialize Result Variable to Zero

3 res = 0

Objective

To set up an accumulator that will hold the XOR of all elements.

Key Insight

Starting with zero is essential because XORing zero with any number returns that number, making zero the identity element for XOR. This allows the accumulator to correctly build the XOR of all elements.

Interview Quick-Check

Core Logic

Initialize the accumulator to zero because zero is the identity for XOR, ensuring the first XOR operation correctly sets the accumulator.

Common Pitfalls & Bugs

Initializing the accumulator to any value other than zero can lead to incorrect results because XOR is not additive but bitwise.

Iterate Through Array and XOR Each Element

To combine all elements using XOR, effectively canceling out duplicates.

Return the Unique Element Stored in Result

To output the single element that appears only once after all duplicates have been canceled.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 5 Critical

res = n ^ res

Update the result by XORing it with the current number.

XORing duplicates cancels them out because n ^ n = 0, and XORing zero with a number returns the number, so after processing all elements, only the unique number remains.

Full line-by-line criticality + rationale for all 4 lines available on Pro.

Test Your Understanding

Why does XORing all elements in the array isolate the unique element?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Single Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Single Number drill

or drill a free problem

1	`class Solution:`
2	`def singleNumber(self, nums: list[int]) -> int:`
3	`res = 0`
4	`for n in nums:`
5	`res = n ^ res`
6	`return res`