LeetCode 1060. Missing Element in Sorted Array

Problem Statement

You're given a sorted array of integers that contains all numbers from 1 to n except one missing number. The task is to find the missing number.

For example:

Input: arr = {1, 2, 3, 4, 6, 7, 8, 9, 10}, n = 10

Output: Missing Number Is: 5

The array contains numbers from 1 to 10, but 5 is missing. Our task is to find the missing number using an efficient approach.

Efficient Solution to Find the Missing Number

To solve this problem in O(n) time complexity, we can use the formula for the sum of the first n natural numbers:

\text{Sum of first n numbers} = \frac{n \times (n+1)}{2}

Once we compute the sum of all numbers from 1 to n, we subtract all the elements in the array from this sum. The remaining value will be the missing number.

Java Code Implementation

Here’s a Java solution to find the missing number:

private static int getMissingNumber(int[] arr, int n) {
		int sum = n*(n+1)/2;
		
		for (int i = 0; i < arr.length; i++) {
			sum -=arr[i];
		}
		
		return sum;
	}

How This Solution Works:

Sum Calculation: We use the formula $n \times (n + 1) / 2$ to calculate the sum of numbers from 1 to n. For example, for n = 10, the sum is $55$ .
Subtraction Loop: Then, we subtract each element of the given array from this sum. The remaining number is the missing one.

For the array {1, 2, 3, 4, 6, 7, 8, 9, 10}, subtracting all the elements from 55 gives us the missing number 5.

Why This Solution is Optimal

Time Complexity: The time complexity of this solution is O(n) because we only traverse the array once to subtract its elements.
Space Complexity: The space complexity is O(1), as we only use a constant amount of extra space for storing the sum.

Enhancing Input Validation

To ensure that the array input is valid (i.e., it has exactly n-1 elements), we can add a check. Here’s an enhanced version of the code:

private static int getMissingNumberEfficiently(int[] arr, int n) {
        // Ensure the array has the correct length (n-1)
        if (arr.length != n - 1) {
            throw new IllegalArgumentException("Array length must be " + (n - 1));
        }

        // Using the sum formula
        int sum = n * (n + 1) / 2;

        // Subtract array elements from sum
        for (int i = 0; i < arr.length; i++) {
            sum -= arr[i];
        }

        return sum;
    }

This version checks if the array length is exactly n-1, which is essential to avoid incorrect input.

Key Takeaways

The formula-based approach is optimal for finding the missing number in a sorted array from a range of numbers.
The solution works efficiently with O(n) time complexity and O(1) space complexity.
Adding input validation makes the program more robust and handles edge cases gracefully.

Frequently Asked Questions

Q: What happens if the array is unsorted?
A: The solution assumes the array is sorted. For unsorted arrays, a different approach like XOR or Hashing can be used to find the missing number.

Q: Can this approach handle large arrays?
A: Yes, this approach works well even for large arrays, provided the sum formula does not result in an overflow for very large values of n. For extreme cases, we might need to use data types with higher capacity, such as long.

Conclusion

Finding a missing number in a sorted array is a common problem that can be efficiently solved using a formula-based approach. The solution provided in Java is simple, optimal, and ensures you can handle arrays of reasonable sizes. By understanding this approach, you'll be better prepared for coding challenges and technical interviews involving similar problems.