LeetCode 136: Single Number — Step-by-Step Visual Trace

#leetcode #python #algorithms

Easy — Bit Manipulation | Array | Math

The Problem

Given an array of integers where every element appears twice except for one, find the single element that appears only once. The solution must run in linear time and use constant extra space.

Approach

Use the XOR bitwise operation which has the property that any number XORed with itself equals zero, and any number XORed with zero equals itself. By XORing all numbers together, the duplicates cancel out leaving only the single number.

Time: O(n) · Space: O(1)

Code

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