Single Number

Problem

https://leetcode.com/problems/single-number/

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.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

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.

Pattern

Bit Manipulation

Approaches

Bit Manipulation

Explanation

Consider what happesn when we take the bitwise XOR of two integers that are the same. Because the binary represenations are identical, the bitwise XOR at every bit will be 0. Now consider what happens if we take the bitwise XOR 0 ^ u where \(u\) is the unique integer in nums. The result is going to be \(u\). Becuase bitwise XOR is commutative and associative, we can bitwise XOR all the numbers in nums regardless of order and obtain the unique integer.

Code

def singleNumber(nums: list[int]) -> int:
    """Return the element that appears only once."""
    result = 0
    for num in nums:
        result ^= num
    return result

Test

>>> from single_number__bit_manipulation import singleNumber
>>> singleNumber([2, 2, 1])
1
>>> singleNumber([4, 1, 2, 1, 2])
4
>>> singleNumber([1])
1

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(n)\)	one pass through the array
Auxiliary Space	\(O(1)\)

single_number__bit_manipulation.singleNumber(nums: list[int]) → int

Return the element that appears only once.