# Missing-Number

Missing-Number

---

## Finding the Missing Number in an Array in Java

When working with arrays, a common problem is finding the missing number from a sequence. Let's dive into how we can solve this problem efficiently in Java.

### Problem Overview

Imagine you are given an array containing `n` distinct numbers taken from the range `0, 1, 2, ..., n`. However, one number from this sequence is missing. Your task is to find the missing number.

For example:

* **Input:** `[3, 0, 1]`
    
* **Output:** `2`
    

### Approach to Solve the Problem

We can solve this problem using a straightforward mathematical approach. The key idea is to calculate the expected sum of the first `n` natural numbers and then subtract the sum of the numbers in the array from this expected sum. The difference will be the missing number.

#### Step-by-Step Explanation:

1. **Expected Sum Calculation**: The sum of the first `n` natural numbers can be calculated using the formula: \[ \\text{Sum} = \\frac{n \\times (n + 1)}{2} \]
    
2. **Actual Sum Calculation**: Iterate through the array to find the sum of the elements present.
    
3. **Find the Missing Number**: Subtract the actual sum from the expected sum to get the missing number.
    

### Java Solution

Here's the Java code implementing this approach:

```java
public 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 using a traditional for loop
        int actualSum = 0;
        for (int i = 0; i < nums.length; i++) {
            actualSum += nums[i];
        }
        
        // 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));
    }
}
```

### Breaking Down the Code

#### Expected Sum Calculation:

```java
int expectedSum = n * (n + 1) / 2;
```

* This line calculates the sum of the first `n` natural numbers using the arithmetic series formula.
    

#### Actual Sum Calculation:

```java
int actualSum = 0;
for (int i = 0; i < nums.length; i++) {
    actualSum += nums[i];
}
```

* Here, we use a traditional `for` loop to iterate over the array and sum up its elements. This loop was originally written using a `for-each` loop, but we've converted it to a traditional `for` loop for clarity.
    

#### Finding the Missing Number:

```java
return expectedSum - actualSum;
```

* Finally, by subtracting the actual sum from the expected sum, we obtain the missing number.
    

### Enhanced for-loop vs. Traditional for-loop

In Java, we often use the enhanced `for-each` loop for simplicity, but it's essential to understand the traditional `for` loop as well. The traditional `for` loop gives more control, allowing us to manipulate the index variable directly, which can be useful in certain scenarios.

Here's how the `for-each` loop would look:

```java
int actualSum = 0;
for (int num : nums) {
    actualSum += num;
}
```

Both versions achieve the same result, but understanding both approaches is valuable, especially when dealing with more complex data structures.

### Conclusion

The missing number problem is a great example of how mathematical concepts can simplify programming challenges. By leveraging the arithmetic sum formula, we efficiently solved the problem with a time complexity of (O(n)) and a space complexity of (O(1)). Additionally, knowing how to switch between `for-each` and traditional `for` loops enhances your flexibility in writing Java code.

---

This blog post not only explains the problem and solution but also highlights the importance of understanding different loop constructs in Java.