Code Logo

Single Number

Published at23 Jul 2026
Created by
Easy 0 views
Like0

Given a non-empty array of integers where every element appears twice except for one element that appears exactly once, find that single element. Your solution must run in linear time and use only constant extra space.

A hash set approach: iterate through the array. If an element is not in the set, add it. If it is already in the set, remove it. At the end, the set contains exactly one element: the one that appeared once.

An XOR approach is more space-efficient (O(1) space), but the hash set approach is also valid and demonstrates understanding of hash-based duplicate detection.

The XOR approach (a XOR a = 0) is more space-efficient: XOR all numbers together, the duplicates cancel out, leaving the single number. This uses O(1) space. Both approaches are valid, but the hash set approach is simpler to understand.

The hash set approach adds each element the first time it is seen and removes it the second time. Elements that appear twice cancel out, leaving only the element that appears once. This works because every element appears either once or twice, and the hash set tracks the state of each element.

An alternative XOR approach is more space-efficient: XOR all numbers together. Duplicates cancel (a XOR a = 0), leaving the single number. However, the hash set approach is easier to understand and debug.

Example Input & Output

Example 1
Input
[1]
Output
1
Explanation

Single element.

Example 2
Input
[2,2,1]
Output
1
Explanation

2 cancels out, 1 remains.

Example 3
Input
[4,1,2,1,2]
Output
4
Explanation

1 and 2 cancel, 4 remains.

Algorithm Flow

Recommendation Algorithm Flow for Single Number
Recommendation Algorithm Flow for Single Number

Solution Approach

Use a hash set. Add if not seen, remove if seen. The remaining element is the answer.

function solution(nums) {
  var seen = {};
  for (var i = 0; i < nums.length; i++) {
    if (seen[nums[i]]) delete seen[nums[i]];
    else seen[nums[i]] = true;
  }
  return Number(Object.keys(seen)[0]);
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int n : nums) {
            if (seen.contains(n)) seen.remove(n);
            else seen.add(n);
        }
        return seen.iterator().next();
    }
}