Find missing number
EasyCompare the expected sum with the real one
Problem
Given an integer array of size n containing distinct values in the range from 0 to n (inclusive), return the only number missing from the array within this range.
Add up 1..n, subtract the sum you actually have — the gap is the missing number.
The idea
The numbers 0..n sum to n(n+1)/2, so subtracting the actual sum leaves exactly the missing value. XOR of all indices against all values works too and cannot overflow, which is why it is often preferred.
The trick
- Sum formula: n(n+1)/2 minus the array sum.
- XOR variant avoids overflow entirely — equal values cancel out.
- O(n) time, O(1) space; no sorting or hash set required.
Step 1 of 5. Brute force: for each number 1..5, scan the array to see if it's there. Values: 1, 2, 4, 5.
Search each candidate.
1for (let c = 1; c <= n; c++) {2 let found = false;3 for (let j = 0; j < n; j++) if (nums[j] === c) found = true;4 if (!found) return c;5}Input
- array
- [1, 2, 4, 5]
Memory
- checking
- —
Output
- checking
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 4, 5], n = 5
- Output:
- 3
- Explanation:
- The numbers 1..5 should be present; 3 is missing.
Example 2
- Input:
- nums = [1, 3], n = 3
- Output:
- 2
- Explanation:
- From 1..3, the number 2 is gone.
Example 3
- Input:
- nums = [2, 3, 4, 5], n = 5
- Output:
- 1
- Explanation:
- 1 is the one left out.
Constraints
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.