[Solved] 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.

Question

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.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Python Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = max(nums)
        s1 = sum(nums)
        s2 = n*(n+1)//2
        if 0 not in nums:
            return 0
        elif s1==s2:
            return n+1
        else:
            return (s2 - s1)
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 514

Leave a Reply

Your email address will not be published. Required fields are marked *