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.length1 <= n <= 1040 <= nums[i] <= nnums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
This approach uses the formula for the sum of the first n natural numbers: Sum = n * (n + 1) / 2. By calculating the sum of the numbers from the array and subtracting it from the expected sum, we can find the missing number.
The above C program calculates the sum of the array elements and subtracts it from the sum of numbers in the range [0, n], which is calculated using the formula n * (n + 1) / 2. This gives the missing number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.
An efficient approach is using XOR. XORing a number with itself results in zero (n ^ n = 0), and XOR of any number with zero keeps the number unchanged (n ^ 0 = n). By XORing all indices and array elements together, each number present in both will cancel out, leaving the missing number.
This C solution utilizes XOR properties: iterates through the array, XORing indices and elements to find the single non-repeated element, which is the missing number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.
| Approach | Complexity |
|---|---|
| Sum Formula Approach | Time Complexity: O(n), where n is the length of the array. |
| Bit Manipulation using XOR | Time Complexity: O(n), iterating through the array. |
Missing Number - Blind 75 - Leetcode 268 - Python • NeetCode • 139,224 views views
Watch 9 more video solutions →Practice Missing Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor