LeetCode 136: Single Number

Meta Data

#

Difficulty: easy First Attempt: 2022-08-16

• Submissions: Accepted ×3

Approach

#

XOR is commutative and associative with x ^ x = 0 and x ^ 0 = x (Bit Manipulation). XOR all numbers: pairs cancel to 0, leaving the single one, in O(1) extra space.

My Solution

#

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

Complexity

#

Time O(n), space O(1).

Mistakes to Avoid

#

• Counting with a hash map works but violates the O(1) space requirement.

Interview Explanation

#

XOR is commutative and a number XORed with itself is 0, so XOR-ing everything cancels the pairs and leaves the answer. Time O(n), space O(1).