Find the missing number in an array containing N-1 distinct numbers taken from the range 1 to N.
Problem Statement
Given an array containing N-1 distinct numbers from the range 1 to N, find the missing number.
Examples
Input: arr = [1, 2, 4, 5], N = 5
Output: 3
Explanation: 3 is missing.
Constraints
Standard constraints
Complexity
Time Complexity: O(N)
Space Complexity: O(1)
Hints
š” Hint 1:
The array contains N - 1 distinct integers from 1 to N.
š” Hint 2:
The sum of the first N natural numbers is given by the formula N * (N + 1) / 2.
š” Hint 3:
Calculate the expected sum and subtract the sum of all elements in the array to find the missing number.
Editorial & Approach
Problem Overview & Intuition
Because the array contains distinct integers from 1 to N with exactly one missing, the missing value is simply the difference between the total expected mathematical sum N * (N + 1) / 2 and the actual sum of elements.
Step-by-Step Approach
- Calculate
expectedSum = (N * (N + 1)) / 2. - Compute
actualSum = arr.reduce((a, b) => a + b, 0). - Return
expectedSum - actualSum.
Optimal Implementation (JavaScript)
function findMissingNumber(arr, N) {
const expectedSum = (N * (N + 1)) / 2;
const actualSum = arr.reduce((acc, val) => acc + val, 0);
return expectedSum - actualSum;
}Complexity Analysis
Time Complexity
O(N) ā single pass to compute the array sum.
Space Complexity
O(1) ā constant extra space.
Edge Cases & Corner Traps Handled
- Missing number is 1 (first element).
- Missing number is N (last element).
- N = 2 with single element array [2] or [1].