The array nums holds n distinct numbers taken from the range 0 to n, so exactly one number from that range is absent. Return the missing number.
Example 1
Input: nums = [3,0,1]
Output: 2
n = 3, so the range is 0 to 3, and 2 is not in the array.
Example 2
Input: nums = [0,1]
Output: 2
n = 2, the range is 0 to 2, and 2 is missing.
Constraints
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All values are distinct
Hints
Frequently asked at: Microsoft, Amazon, Apple, TCS, Cognizant
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting and scanning for the gap is O(n log n), and a hash set costs O(n) space. If no number were missing, the values would be exactly 0..n, whose sum is n * (n + 1) / 2. The difference between that and the actual sum is the missing number. The XOR version pairs each index with each value so everything cancels except the missing one.
Algorithm
- Let
n = nums.length. - Compute
expected = n * (n + 1) / 2. - Subtract every element from
expected. - Return what is left.
Time:
O(n)Space: O(1)Interview tip: For large
n the sum can overflow a 32-bit int in Java or C++. Mention the XOR method (ans ^= i ^ nums[i], starting from ans = n) as the overflow-safe answer.class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) return n * (n + 1) // 2 - sum(nums) # expected sum minus actual sumCtrl + Enter runs the examples