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.

Single Number - LeetCode Solution & Explanation

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.

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

Recognizing the XOR properties allows a linear time and constant space solution. By XORing all elements, duplicates cancel out. This insight transforms the problem from counting frequencies to a simple bitwise reduction.

Optimal Approach

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.

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.

Solution

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

1import java.util.List;
2
3public class Solution {
4    public int singleNumber(List<Integer> nums) {
5        int res = 0;
6        for (int n : nums) {
7            res = n ^ res;
8        }
9        return res;
10    }
11}

1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7    int singleNumber(const vector<int>& nums) {
8        int res = 0;
9        for (int n : nums) {
10            res = n ^ res;
11        }
12        return res;
13    }
14};

1var singleNumber = function(nums) {
  let res = 0;
  for (const n of nums) {
      res = n ^ res;
  }
  return res;
7};

Step-by-Step Solution

1

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.

2

Iterate Through Array and XOR Each Element

4for n in nums:
5    res = n ^ res

Objective

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

Key Insight

XOR is commutative and associative, so the order of operations does not matter. Each pair of identical numbers XOR to zero, so after processing all elements, only the unique number remains in the accumulator.

Interview Quick-Check

Core Logic

XOR all elements in a single pass to cancel out duplicates and isolate the unique element.

State & Boundaries

The loop must process every element exactly once to ensure all duplicates are canceled.

Common Pitfalls & Bugs

Forgetting that XOR is its own inverse or misusing XOR operations can lead to incorrect results.

3

Return the Unique Element Stored in Result

6	`return res`

Objective

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

Key Insight

After XORing all elements, the accumulator holds the unique element because all duplicates have canceled out to zero.

Interview Quick-Check

Core Logic

Return the accumulator after processing all elements as it contains the unique number.

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.

Line 3 Core

res = 0

Initialize the result variable to zero to serve as the XOR accumulator.

Zero is the identity element for XOR, so starting with zero ensures the first XOR operation correctly sets the accumulator without altering the result.

Line 6 Core

return res

Return the accumulated result which holds the unique element.

After all XOR operations, the accumulator contains the single number that does not have a duplicate, fulfilling the problem's requirement.

Line 4 Standard

for n in nums:

Begin iterating through each number in the input array.

Processing every element is necessary to combine all values via XOR, ensuring duplicates cancel out and the unique element remains.

Test Your Understanding

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

Because XORing a number with itself results in zero, all duplicate elements cancel out, and XORing zero with the unique element returns the unique element itself.

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`

1	`import java.util.List;`
2
3	`public class Solution {`
4	`public int singleNumber(List<Integer> nums) {`
5	`int res = 0;`
6	`for (int n : nums) {`
7	`res = n ^ res;`
8	`}`
9	`return res;`
10	`}`
11	`}`

1	`#include <vector>`
2
3	`using namespace std;`
4
5	`class Solution {`
6	`public:`
7	`int singleNumber(const vector<int>& nums) {`
8	`int res = 0;`
9	`for (int n : nums) {`
10	`res = n ^ res;`
11	`}`
12	`return res;`
13	`}`
14	`};`

1	`var singleNumber = function(nums) {`
2	`let res = 0;`
3	`for (const n of nums) {`
4	`res = n ^ res;`
5	`}`
6	`return res;`
7	`};`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Result Variable to Zero

Iterate Through Array and XOR Each Element

Return the Unique Element Stored in Result

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.