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
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 if tmp else len(nums)
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 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.