0268.Missing_Number.py

"""
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
 

Constraints:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.

"""

"""
solution 3: add every num together and compare with n(n+1)/2
O(1)
"""
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (len(nums) + 1) * len(nums) // 2 - sum(nums) 

   
"""
solution 1: 448类似的做法，我们通过nums[i] += 1来get rid of the 0s.
"""
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        
        for i in range(n):
            nums[i] += 1    # get rid of 0, cuz -0 = 0, which is not good for us to tell if it has been marked as negative or not
        
        # 1st pass: change num to negative 
        for num in nums:
            idx = abs(num) - 1
            if idx == n:
                continue
            nums[idx] = -abs(nums[idx])
            
        # 2nd pass: find the positive number, then the corresponding idx is the missing number
        for i, num in enumerate(nums):
            if num > 0:
                return i
            
        return n