Code Logo

Single Number

Published at23 Jul 2026
Created by
Easy 1 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

Solution Approach

Given an array of integers, return the element that appears only once. All other elements appear exactly twice. Use XOR: a number XORed with itself is 0, and XOR is commutative. XORing all elements together cancels out the duplicates, leaving the single element.

function singleNumber(nums) {
  var result = 0;
  for (var i = 0; i < nums.length; i++) {
    result ^= nums[i];
  }
  return result;
}

The XOR operator has the property that a ^ a = 0 and a ^ 0 = a. By XORing all elements in the array, every pair of identical numbers cancels out to 0, and the remaining value is the element that appears only once.

Time complexity is O(n), space complexity is O(1).

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();
    }
}