Single Number

Easy Problem 145 of 151 Java and Python

Practice on LeetCode

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Use linear time and only constant extra space.

Example 1

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

Example 2

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

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
Each element appears twice except for one, which appears once.

Explanation

XOR has three useful properties: x ^ x = 0, x ^ 0 = x, and order does not matter. XOR all the numbers together and every pair cancels out, leaving the single number.

Approach 1 · Naive

Hash set of unmatched numbers

Time O(n)
Space O(n)

Add a number when you see it and remove it when you see it again. The one left is the answer.

For each number: if it is in the set, remove it; otherwise add it.
Return the only element left.

Java

import java.util.*;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> unmatched = new HashSet<>();
        for (int num : nums) {
            if (!unmatched.remove(num)) {
                unmatched.add(num);
            }
        }
        return unmatched.iterator().next();
    }
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        unmatched = set()
        for num in nums:
            if num in unmatched:
                unmatched.remove(num)
            else:
                unmatched.add(num)
        return unmatched.pop()

Approach 2 · Optimal

XOR everything

Time O(n)
Space O(1)

Pairs cancel under XOR, so the XOR of all numbers is the single one.

result = 0.
For each number, result ^= num.
Return result.

Java

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

Complexity compared

Approach	Time	Space
Naive Hash set of unmatched numbers	O(n)	O(n)
Optimal XOR everything	O(n)	O(1)

Key takeaways

"Everything appears twice except one" almost always means XOR.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem