I see many people use sum to find the missing number, but what if n is large and (n+1)*n overflows? At least they should use a long I think. Here I give two different solutions

**Edit: seems overflow does not matter in the problem, even if the (n+1) n overflows, we can still get the right answer because the sum of the numbers also overflows*

**solution 1:**

put i to nums[i], then find the missing number

```
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
x=nums[i]
while x!=i and x!=len(nums) and nums[x]!=x:
nums[i],nums[x]=nums[x],nums[i]
x=nums[i]
tmp=[i for i in range(len(nums)) if nums[i]!=i]
return tmp[0] if tmp else len(nums)
```

**solution2:**

because every number is non-negative, we could set nums[i] to be negative if i exists.

```
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
x=-(nums[i]+1) if nums[i]<0 else nums[i]
if x<len(nums):
nums[x]=-nums[x]-1
tmp=[i for i in range(len(nums)) if nums[i]>=0]
return tmp[0] if tmp else len(nums)
```