Q: Missing Number
Description：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
A1: Bit Manipulation
Intuition
We can harness the fact that XOR is its own inverse to find the missing element in linear time.
Algorithm
Because we know that nums containsnnumbers and that it is missing exactly one number on the range [0..n-1] , we know thatndefinitely replaces the missing number in nums. Therefore, if we initialize an integer tonand XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 0 | 1 | 3 | 4 |
Python3
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
Complexity Analysis
-
Time complexity : O(n)
Assuming that XOR is a constant-time operation, this algorithm does constant work on nn iterations, so the runtime is overall linear.
-
Space complexity : O(1)
This algorithm allocates only constant additional space.
A2：Gauss' Formula
Intuition
One of the most well-known stories in mathematics is of a young Gauss, forced to find the sum of the first 100 natural numbers by a lazy teacher. Rather than add the numbers by hand, he deduced a closed-form expression for the sum, or so the story goes. You can see the formula below:
Algorithm
We can compute the sum of nums in linear time, and by Gauss' formula, we can compute the sum of the first n natural numbers in constant time. Therefore, the number that is missing is simply the result of Gauss' formula minus the sum of nums, as nums consists of the first n natural numbers minus some number.
Python3
class Solution:
def missingNumber(self, nums):
expected_sum = len(nums)*(len(nums)+1)//2
actual_sum = sum(nums)
return expected_sum - actual_sum
Complexity Analysis
-
Time complexity :
O(n)Although Gauss' formula can be computed in
O(1)time, summingnumscosts usO(n)time, so the algorithm is overall linear. Because we have no information about which number is missing, an adversary could always design an input for which any algorithm that examines fewer thannnumbers fails. Therefore, this solution is asymptotically optimal. Space complexity :
O(1)
This approach only pushes a few integers around, so it has constant memory usage.
