Single Number

Single Number

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

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

Using a HashSet (linear space complexity)

We can iterate nums and for each number n do the following:

1. If this is the first time we’ve seen n, then we add n to a hashset
2. If the hashset contains n, then n gets removed from the hashset:

def get_single_number(nums: List[int]) -> int:
    uniques = set()
    for n in nums:
        if n not in uniques:
            uniques.add(n)
        else:
            uniques.remove(n)
    return uniques.pop()

This algorithm has O(n) time and space complexity.

Using XOR (constant space complexity)

Making use of the following facts about the XOR operator:

1. XOR is commutative and associative.
2. x ^ x = 0
3. 0 ^ x = x

it’s not hard to see that when we apply xor on all numbers in nums we get the single number:

from functools import reduce
from operator import xor

def get_single_number(nums: List[int]) -> int:
    return reduce(xor, nums)

The XOR approach uses constant extra space.

Extension

So far we’ve assumed that the single number appears exactly once and everything else appears twice. The two approaches above still work if we loosen the problem statement as follows:

Given a non-empty array of integers `nums`, every element appears even number of times except for one number which appears odd nunber of times.
Find the one that appears odd number of times.

Let’s consider the following problem.

Find the Difference

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:    
Input: s = "", t = "y"
Output: "y"

Example 3:
Input: s = "a", t = "aa"
Output: "a"

Example 4:
Input: s = "ae", t = "aea"
Output: "a"

Application of the XOR pattern

Define u to be the concatenation of s and t. Since t is a permutation of s plus an extra letter, it’s easy to see that the unique letter that we are trying to find appears odd number of times in u and the rest appear even number of times in u:

def find_the_difference(s: str, t: str) -> str:
    current = 0
    for char in s:
        current ^= ord(char)
    for char in t:
        current ^= ord(char)
    return chr(current)

To fully internalize the XOR pattern, let’s consider the following variation.

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:    
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:
Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Reduction to Single Number

Define arr to be the concatenation of nums and all numbers in the range [0, n]. Notice that the number we are looking for appears once in arr and the rest appear twice in arr. We’ve therefore reduced this problem into the original Single Number problem:

def get_missing_number(nums: List[int]) -> int:
    missing = len(nums)
    for i, n in enumerate(nums):
        missing ^= n
        missing ^= i
    return missing