Single Number

Share

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 linear runtime complexity and use only constant extra space.

Example 1
Input: nums = [2, 2, 1]
Output: 1
Explanation: 1 appears only once, while 2 appears twice.
Example 2
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 4 appears only once; 1 and 2 each appear twice.

Solution Approach

The key insight is the XOR property: a ^ a = 0 and a ^ 0 = a. XOR-ing all numbers together cancels out pairs, leaving only the single number.

  • Initialize result to 0.
  • XOR every number in the array with the result.
  • Since duplicate numbers cancel out (x ^ x = 0), only the unique number remains.
Java
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}
Complexity Analysis:

Time complexity: O(n). Single pass through the array.
Space complexity: O(1). Only one variable used.