Single Number

Problem Description

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

Examples

Constraints

• 1 ≤ nums.length ≤ 3 * 10⁴
• -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴
• Each element in the array appears twice except for one element which appears only once.

XOR Cancellation Property

The XOR operation ^ has three properties:

1. x ^ 0 = x
2. x ^ x = 0
3. XOR is commutative and associative: a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b.

If we XOR all numbers in the array together, every pair of duplicate numbers will cancel out to 0. The only number left will be the unique one.

Solution: XOR Scan

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

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

#include <vector>

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the array length. We make a single pass over the elements.
• Space Complexity: O(1) extra space.

← All Problems