Two different solutions without using sum


  • 0
    Y

    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)

  • 0

    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.


  • 0
    Y

    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.


  • 0

    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)

Log in to reply
 

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