268_Missing Number
[Easy][Array, Math, Bit Manipulation]
Given an array containing n distinct numbers taken from0, 1, 2, ..., n
, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Solution 1:
Idea:
Sort the array in ascending order.
Loop over each element, find which element doesn't equal to it's index.
Time Complexity:
Space Complexity:
def missingNumber(nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
i = 0
while i < len(nums):
if i != nums[i]:
return i
else:
i += 1
return nums[-1] + 1
Solution 2:
Idea:
Use math summation formula.
If there is no element missing, adding from 0 to n gives .
Loop over each element in the array to get the summation. The difference between the expected summation and real summation will be the element missing.
Time Complexity:
Space Complexity:
def missingNumber(nums):
"""
:type nums: List[int]
:rtype: int
"""
sums = 0
for i in range(len(nums)):
sums += nums[i]
n = len(nums)
return n*(n+1)/2 - sums
Last updated
Was this helpful?