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:
- If this is the first time we’ve seen
n
, then we addn
to a hashset - If the hashset contains
n
, thenn
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:
- XOR is commutative and associative.
x ^ x = 0
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