Missing Number
Problem
The array holds n distinct numbers from the range 0..n, so exactly one is missing. Return it, in O(n) time and O(1) space.
Example 1
Input: [3, 0, 1] Output: 2
Example 2
Input: [9, 6, 4, 2, 3, 5, 7, 0, 1] Output: 8
Test cases
Case 1
Input: [3,0,1] Expected: 2
Case 2
Input: [0,1] Expected: 2
Case 3
Input: [9,6,4,2,3,5,7,0,1] Expected: 8
View solutionHide solution2 approaches
1. Sum formula
Time O(n)Space O(1)
Expected sum of 0..n minus the actual sum.
function missingNumber(nums) { const n = nums.length; return (n * (n + 1)) / 2 - nums.reduce((a, b) => a + b, 0);}2. XOR
Time O(n)Space O(1)
XOR every index and every value; pairs cancel, the missing number remains. No overflow risk.
function missingNumber(nums) { let x = nums.length; for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]; return x;}