Missing Number

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}