Solution 1 - Gauss' Formula (Math)
Missing = n*(n+1)/2 - sum(nums).
""" 0268.1 - Missing Number - Solution 1 - Gauss' Formula """
from typing import List
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
if __name__ == "__main__":
print(Solution().missingNumber([3,0,1]))Solution 2 - XOR
XOR indices and values; duplicates cancel.
from typing import List
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i, x in enumerate(nums):
res ^= i ^ x
return res