Find the Missing Number in a Sequence
Solve this Problem
You're given an array
nums containing n distinct numbers, all drawn from the range 0 to n inclusive. Exactly one number from that range never made it into the array — find and return it.
Think about what the numbers 0 through n *should* add up to, and compare that against what they actually add up to in the given array.
Test Case 1:
Input:nums = [0, 1, 3, 4, 5]
Output:2
Explanation:The full range is 0 to 5, and 2 is the one value not present.
Test Case 2:
Input:nums = [1]
Output:0
Explanation:With n = 1 the range is 0 to 1; only 1 appears, so 0 is missing.
Test Case 3:
Input:nums = [0, 1, 2, 3, 4]
Output:5
Explanation:The range is 0 to 5, and the array stops one short at 4.
Constraints
- ◆
1 ≤ n ≤ 10⁵, where n = nums.length - ◆
nums contains n distinct numbers taken from the range [0, n] - ◆
Exactly one number in that range is absent from nums
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int findMissingNumber(int[] nums) { |
| 3 | int n = nums.length; |
| 4 | int expected = n * (n + 1) / 2; |
| 5 | int actual = 0; |
| 6 | for (int num : nums) actual += num; |
| 7 | return expected - actual; |
| 8 | } |
| 9 | } |
| 10 |
0
1
3
4
5
0
1
2
3
4
Variables
n
5expected
15n = nums.length = 5
expected = n × (n + 1) / 2
= 5 × 6 / 2
= 15
CALCULATE
If nothing were missing, the numbers 0 through 5 would sum to 15 — that's what expected holds.
Step 1 / 3
Approach & Solutions
Brute Force — Search for Each Candidate
BruteFor every candidate value from 0 to n, scan the whole array looking for it. The candidate that's never found is the missing number. Correct, but re-scanning the array for every candidate wastes work.
Time
O(n²)Space
O(1)Java
1class Solution {
2 public int findMissingNumber(int[] nums) {
3 int n = nums.length;
4 for (int candidate = 0; candidate <= n; candidate++) {
5 boolean found = false;
6 for (int num : nums) {
7 if (num == candidate) { found = true; break; }
8 }
9 if (!found) return candidate;
10 }
11 return -1;
12 }
13}Optimal — Sum Formula
OptimalThe numbers 0 through n should sum to n·(n+1)/2 if none were missing. Subtract the array's actual sum from that expected sum — whatever is left over is exactly the value that never made it into the array.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int findMissingNumber(int[] nums) {
3 int n = nums.length;
4 int expected = n * (n + 1) / 2;
5 int actual = 0;
6 for (int num : nums) actual += num;
7 return expected - actual;
8 }
9}