Missing Number

The "Missing Number" problem is a common problem in algorithm and coding challenges. Here’s a breakdown of the problem and how to solve it:

Problem Description:

You are given an array containing n distinct numbers taken from the range 0, 1, 2, ..., n. Since the array contains n numbers but is taken from the range of n+1 numbers, one number in this range is missing. The goal is to find the missing number.

For example:

• Input: [3, 0, 1]

• Output: 2

Explanation:

Given the array [3, 0, 1], the array should ideally contain the numbers 0, 1, 2, 3. However, 2 is missing, so the function should return 2.

Approach to Solve the Problem:

1. Sum Formula Approach:

   • The sum of the first n natural numbers is given by the formula: Sum=n×(n+1)2\text{Sum} = \frac{n \times (n + 1)}{2}Sum=2n×(n+1)​

   • Calculate the expected sum of the first n natural numbers.

   • Subtract the sum of all elements in the given array from this expected sum. The difference will be the missing number.

Java Solution:

javaCopy codepublic class MissingNumber {
    public static int findMissingNumber(int[] nums) {
        int n = nums.length;
        // Calculate the sum of the first n natural numbers
        int expectedSum = n * (n + 1) / 2;

        // Calculate the sum of the numbers present in the array
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }

        // The missing number is the difference between expectedSum and actualSum
        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] nums = {3, 0, 1};
        System.out.println("The missing number is: " + findMissingNumber(nums));
    }
}

How It Works:

1. Expected Sum: For an array of size n = 3, the sum of the numbers from 0 to 3 should be 3×42=6\frac{3 \times 4}{2} = 623×4​=6.

2. Actual Sum: The sum of the elements in the array [3, 0, 1] is 3 + 0 + 1 = 4.

3. Missing Number: The missing number is calculated as Expected Sum - Actual Sum = 6 - 4 = 2.

This solution has a time complexity of O(n)O(n)O(n) and a space complexity of O(1)O(1)O(1), making it very efficient.