Problem statement
An array contains n - 1 distinct numbers from 1 through n. Return the missing number.
For n = 5 and [1, 2, 4, 5], the answer is 3.
Constraints & requirements
- INPUT
- Distinct values from 1 through n
- MISSING
- Exactly one range value
- TARGET
- Linear time and constant space
Examples 3 test cases
Example 1 Middle missing
- Input
[1, 2, 4, 5], n = 5- Output
3
Checks cancellation in the middle.
Example 2 First missing
- Input
[2, 3], n = 3- Output
1
Checks the lower boundary.
Example 3 Last missing
- Input
[1, 2, 3], n = 4- Output
4
Checks the upper boundary.
Hints Optional
01Look for cancellation
For any integer x, x XOR x becomes 0 and x XOR 0 remains x.
02Include both sets of values
XOR every expected number from 1 through n and every value present in the array.
03Use the indexes
Start answer at n, then XOR index + 1 and values[index] in the same loop.
How to think before coding
The input promises distinct values from 1 through n, with exactly one absent. Start from the slow presence check, then look for cancellation rather than a data structure: every present value appears once in the expected range and once in the input. XOR removes those pairs. Include n separately because the n−1 array positions supply only expected values 1 through n−1.
Brute force and the improvement
Scan the array separately for each value in 1..n: O(n²) time, O(1) space. A boolean presence array improves that to O(n) time with O(n) space. A sum difference also uses O(n) time and O(1) space if you calculate ((long) n * (n + 1L)) / 2 and the actual sum as long, not int. XOR reaches the same bounds without arithmetic overflow under the distinct-value contract.
Intuition
XOR has two useful properties: x ^ x is zero, and x ^ 0 is x. If we XOR every expected number with every number in the array, matching values cancel and the missing value remains.
Java solution
public static int missingNumber(int[] values, int n) {
int answer = n; // Include n; n−1 loop indexes provide expected values 1..n−1.
for (int index = 0; index < values.length; index++) {
answer ^= index + 1; // Include one expected range value.
answer ^= values[index]; // Include one present value; equal values cancel.
}
return answer; // Only the missing number occurs once across the two sets.
}Why not use the sum formula
The expected sum minus the actual sum is also correct, but an int sum can overflow for large input. XOR avoids that issue.
Dry run

Read the text transcript
For n = 5 and [1, 2, 4, 5], start with answer = 5.
| Index | XOR expected | Answer then | XOR present | Answer afterward |
|---|---|---|---|---|
| 0 | 1 | 4 | 1 | 5 |
| 1 | 2 | 7 | 2 | 5 |
| 2 | 3 | 6 | 4 | 2 |
| 3 | 4 | 6 | 5 | 3 |
The intermediate accumulator is not a partial missing-number answer. Cancellation guarantees the final result 3 only after including both complete sets.
Complexity
Time is O(n) and extra space is O(1).
Common mistake
Make sure the expected range matches the problem. Some versions use values from 0 through n, while this version uses 1 through n.
Practice next
Next lessonLongest Subarray with Sum KPractice using stored state to avoid repeated work.