Single Number

Bit ManipulationArray

EasyLeetCode #136

10 min

Problem Statement

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

Examples

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

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

Output: 4

Solution (XOR)

Similar to the "Missing Number" problem, the XOR operator is the key to an elegant and efficient solution. Since every number appears twice except for one, we can leverage the property that a ^ a = 0.

Algorithm Steps

Initialize a variable result to 0.
Iterate through each number in the nums array.
In each iteration, XOR the result with the current number.
After the loop, all the numbers that appear twice will have cancelled each other out (because x ^ x = 0).
The result will hold the value of the single number that did not have a pair.

Array `nums`:

result: 0000 (0)

Initialize result = 0

Single Number Solution


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