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

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments