LC 136 - Single Number

Question

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 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Links

Question here and solution here

Solution

concept

In order to get $O(1)$ space we need to use XOR, which only output True if the input differ.

XOR Truth Table

A	B	A^B
F	F	F
F	T	T
T	F	T
T	T	F

This has 2 relevant consequences here:

1. if we XOR two identical number, it will be 0
2. if we XOR any number with 0, we will get back the same number This means that we can just XOR all the value (since XOR is associative and commutative), and whatever that is left is our number.

code

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

Complexity

time: $O(n)$
space: $O(1)$