DSA problem
Find the Missing Number (1 to N)
Given an array containing N - 1 distinct integers in the range [1, N], find the one missing number.
There are two elegant O(N) solutions. The math approach: the sum of 1 to N is N * (N + 1) / 2. Sum all elements and subtract from this formula - the difference is the missing number. The XOR approach: XOR all numbers from 1 to N, then XOR with all array elements; since a XOR a = 0, every number cancels except the missing one.
Both run in O(N) time and O(1) space. This teaches you to leverage mathematical properties for optimal solutions instead of sorting and scanning in O(N log N).
Examples
Example 1
Input:
n = 5, nums = [1, 2, 4, 5]Output:
3Explanation: The full range [1, 5] is {1, 2, 3, 4, 5}; 3 is the value absent from the array.
Constraints
- 2 <= n <= 10^5
- nums contains n - 1 distinct integers from the range [1, n]
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.