-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path268.py
More file actions
44 lines (33 loc) · 961 Bytes
/
268.py
File metadata and controls
44 lines (33 loc) · 961 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
268. Missing Number
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?
'''
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if (len(nums) == 0):
return 0
sumA = 0
for i in range(len(nums) + 1):
sumA += i
sumB = 0
for num in nums:
sumB += num
return (sumA - sumB)
def missingNumberB(self, nums):
n = len(nums)
return reduce(operator.xor, nums) ^ [n, 1, n+1, 0][n % 4]
if __name__ == "__main__":
a = [0, 1, 3, 4, 5, 6]
sol = Solution()
ret = sol.missingNumber(a)
print(ret)