# Two different solutions without using sum

• 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)``````

• Um, Python ints don't have an overflow problem anyway. You might want to use your approach with a language where it actually makes a difference.

• I know python's int doesn't overflow, but I think in many problems we should assume int in python would overflow, otherwise some problems would be too easy for python.

• Hmm, I don't think so. Maybe in the few problems where it would really make a huge difference, but not really in a case like this where in other languages you can just use long.

Btw, another solution I thought of after seeing yours:

``````def missingNumber(self, nums):
x = range(len(nums) + 1)
for num in nums:
x[num] = 0
return max(x)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.