Understanding the Problem
We are given an array of size N - 1
that contains distinct integers ranging from 1
to N
. But one number is missing. Our task is to figure out which number is missing from the array.
Let’s understand this intuitively. If no number was missing, then the sum of all numbers from 1 to N would be:
Expected Sum = N * (N + 1) / 2
If we subtract the actual sum of the given array from this expected sum, the difference will be the missing number.
Step-by-Step Walkthrough
Example: Find the Missing Number from [1, 2, 4, 5], where N = 5
- Step 1: Calculate expected sum = 5 × (5 + 1) / 2 = 15
- Step 2: Calculate actual sum = 1 + 2 + 4 + 5 = 12
- Step 3: Missing number = 15 - 12 = 3
So, 3 is the missing number.
Incorporating Edge Cases with Intuition
1. First Number Missing
Array = [2, 3, 4, 5], N = 5
Expected = 15, Actual = 14 ⇒ Missing = 1
This works because the formula always includes the first number. If it’s missing, the difference will reflect that.
2. Last Number Missing
Array = [1, 2, 3, 4], N = 5
Expected = 15, Actual = 10 ⇒ Missing = 5
The formula ensures we’re not depending on array order, so even the last number being missing is handled smoothly.
3. Only One Element in Array
Array = [1], N = 2
Expected = 3, Actual = 1 ⇒ Missing = 2
This proves our approach is valid even for the smallest possible size of input.
4. Empty Array
Array = [], N = 1
Expected = 1, Actual = 0 ⇒ Missing = 1
This is the edge case with the smallest possible value of N. Still, our formula gives the correct result.
5. Random Order
Array = [3, 1, 5, 2], N = 5
Expected = 15, Actual = 11 ⇒ Missing = 4
Since addition is commutative, the order of numbers doesn't matter. This makes our approach robust even when the array isn't sorted.
Why This Works
We are using math to solve the problem in a single pass over the array. This makes the solution:
- Time Complexity: O(N) – because we sum the array once
- Space Complexity: O(1) – no extra memory is needed
We don't need extra data structures like hash sets or frequency counters. The formula handles all cases efficiently, and it's especially useful for large datasets.
Comments
Loading comments...