# 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:

```java
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.