Log inSign up
easyLeetCodeNot Started

Single Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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 O(n) and use only constant extra space O(1).

Example 1 · Example 1: Short Array:

Input: nums = [2, 2, 1]
Output: 1
Explanation: 2 ^ 2 ^ 1 = 0 ^ 1 = 1.

Example 2 · Example 2: Five Elements:

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

Example 3 · Example 3: Single Element Array:

Input: nums = [1]
Output: 1
Explanation: Only 1 is present, returns 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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the commutative and self-inverse algebraic properties of bitwise XOR.
  • Achieve optimal O(n) time and O(1) space cancellation.
  • Extend pair-cancellation logic to more general single-number variants.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Every element appears twice except one unique element.
  • Linear time O(n) and constant space O(1) constraints.
  • Pair cancellation problem.

Algorithmic Decision Tree:

  • Initialize res = 0.
  • Iterate num in nums: res ^= num.
  • Return res.

Connected Patterns:

Single Number IISingle Number IIIMissing Number

1. Hash Set Tracking

Intuition

Iterate through nums. If x is in the set, remove it. Otherwise, add x. At the end of the array, the set contains only the single element.

When to apply: Basic demonstration of frequency tracking.

Algorithm

  1. Step 1: Create an empty set.
  2. Step 2: For each num: if in set, remove; else, add.
  3. Step 3: Return the only element remaining in the set.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5using namespace std;
6
7int singleNumberSet(const vector<int>& nums) {
8 unordered_set<int> s;
9 for (int x : nums) {
10 if (s.count(x)) s.erase(x);
11 else s.insert(x);
12 }
13 return *s.begin();
14}
15
16int main() {
17 vector<int> nums = {4, 1, 2, 1, 2};
18 cout << "Set: " << singleNumberSet(nums) << endl; // 4
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

2. Mathematical Sum Identity

Intuition

The sum of unique elements doubled minus the sum of all elements in the array cancels out all elements that appear twice, isolating the single element.

When to apply: Alternative conceptual approach.

Algorithm

  1. Step 1: Compute sumOfAll = sum(nums).
  2. Step 2: Compute sumOfUnique = sum(set(nums)).
  3. Step 3: Return 2 * sumOfUnique - sumOfAll.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <numeric>
5
6using namespace std;
7
8int singleNumberMath(const vector<int>& nums) {
9 unordered_set<int> s(nums.begin(), nums.end());
10 long long sumUnique = accumulate(s.begin(), s.end(), 0LL);
11 long long sumAll = accumulate(nums.begin(), nums.end(), 0LL);
12 return (int)(2 * sumUnique - sumAll);
13}
14
15int main() {
16 vector<int> nums = {4, 1, 2, 1, 2};
17 cout << "Math: " << singleNumberMath(nums) << endl; // 4
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

3. Cumulative Bitwise XOR

Intuition

Initialize res = 0. Iterate through all numbers in nums, accumulating res ^= x. All duplicate pairs cancel each other out to 0 because x ^ x = 0. The remaining value in res is the unique single number.

When to apply: Optimal canonical solution for Single Number.

Algorithm

  1. Step 1: Set res = 0.
  2. Step 2: For each x in nums: res ^= x.
  3. Step 3: Return res.

XOR Accumulation Trace: nums = [4, 1, 2, 1, 2]

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Step 1: res = 0 ^ 4 = 4
Visual state
Values and pointers at this exact step
pointers
S
4
0
↑ nums[0] = 4
Check / comparison
res = 4
Decision / next transition
First element loaded.
Why this step matters

Step 1: res = 0 ^ 4 = 4.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int singleNumber(vector<int>& nums) {
9 int res = 0;
10 for (int x : nums) {
11 res ^= x;
12 }
13 return res;
14 }
15};
16
17int main() {
18 Solution sol;
19 vector<int> nums = {4, 1, 2, 1, 2};
20 cout << "Optimal XOR: " << sol.singleNumber(nums) << endl; // 4
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set TrackingO(n)O(n)Add elements to a set; if already present, remove. The set will contain only the single element.Set memory allocation.
2.Better — Math Sum IdentityO(n)O(n)2 * sum(set(nums)) - sum(nums) = single_number.Set construction and summation.
3.Optimal — Cumulative Bitwise XOROptimalO(n)O(1)Accumulate XOR across all elements. Paired duplicates cancel out to 0, leaving the single element.Single linear pass.

Common Pitfalls & Crucial Edge Cases

Allocating a frequency hash map

Violates the O(1) auxiliary space constraint.

Initializing the accumulator to 1 instead of 0

Must initialize result = 0 because 0 ^ x = x.

Assuming inputs are sorted

Never assume input ordering without sorting first.

Crucial Edge Cases to Validate:

  • Array of length 1 `[x]` — Loop does 1 iteration; returns x.
  • Single number is negative (e.g. `[2, 2, -1]`) — XOR works identically for negative integers in two's complement; returns -1.
  • Single number is 0 (e.g. `[4, 1, 2, 1, 2, 4, 0]`) — Correctly returns 0.
  • Large array with 10^5 elements — Linear pass processes in a fraction of a millisecond.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the mathematical properties of XOR concisely: A ^ A = 0 and A ^ 0 = A.
  2. Contrast this with arithmetic summation (2 * sum(set) - sum(nums)) and point out how XOR avoids integer overflow.
  3. Mention that this pattern generalizes to finding two unique numbers (Single Number III) and missing numbers.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Which properties of the bitwise XOR operator make it ideal for finding the single non-duplicate number?

2.What is the time and auxiliary space complexity of the XOR solution for Single Number?

3.Why is a Hash Set or Sorting approach inferior in an interview setting?

Back to DSA Sheet