# Missing Number

{% hint style="info" %}
Array, Iterative Approach 
{% endhint %}

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return *the only number in the range that is missing from the array.*

 

**Example 1:**

<pre data-full-width="true"><code><strong>Input: nums = [3,0,1]
</strong><strong>Output: 2
</strong><strong>Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
</strong></code></pre>

**Example 2:**

<pre data-full-width="true"><code><strong>Input: nums = [0,1]
</strong><strong>Output: 2
</strong><strong>Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
</strong></code></pre>

**Example 3:**

<pre data-full-width="true"><code><strong>Input: nums = [9,6,4,2,3,5,7,0,1]
</strong><strong>Output: 8
</strong><strong>Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
</strong></code></pre>

&#x20;

**Constraints:**

* `n == nums.length`
* `1 <= n <= 104`
* `0 <= nums[i] <= n`
* All the numbers of `nums` are **unique**.

### Solutions

#### Approach - Brute Force Technique

This solution is considered a brute force approach because it checks each candidate number against all numbers in the array.

**Steps**

1. **Outer Loop**: The outer loop iterates over all numbers from 0 to `nums.Length`. Each number in this range is a potential candidate for the missing number.
2. **Inner Loop and Flag Initialization**: For each candidate number, a boolean flag `found` is initialized to `false`, and an inner loop iterates over all numbers in the array `nums`.
3. **Number Checking**: Inside the inner loop, it checks if the current number in the array `nums` is equal to the candidate number. If it is, it sets `found` to `true` and breaks the inner loop.
4. **Missing Number Identification**: After the inner loop, it checks the flag `found`. If `found` is still `false`, it means the candidate number was not found in the array `nums`, so it returns the candidate number as the missing number.
5. **Completion**: The function continues this process until it finds a missing number or it has checked all candidate numbers. If it has checked all candidate numbers and hasn’t found a missing number, it returns -1. However, according to the problem statement, there should always be one missing number, so this line should never be reached.

```csharp
public class Solution {
    public int MissingNumber(int[] nums) {
        for (int i = 0; i <= nums.Length; i++) {
            bool found = false;
            for (int j = 0; j < nums.Length; j++) {
                if (nums[j] == i) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return i;
            }
        }
        return -1; // This line should never be reached.
    }
}

```

> Complexity

* **Time Complexity:** O(N^2)
* **Auxiliary Space:** O(1)

#### Approach - Iterative Technique

**Steps**

1. **Expected Sum Calculation**: The function calculates the expected sum of all numbers from 0 to `nums.Length` using the formula for the sum of an arithmetic series: `nums.Length*(nums.Length+1)/2`. This sum is stored in `expectedSum`.
2. **Actual Sum Calculation**: The function then calculates the actual sum of all numbers in the array `nums` by iterating over each number in `nums` and adding it to `actualSum`.
3. **Missing Number Calculation**: Finally, the function calculates the missing number by subtracting `actualSum` from `expectedSum`. The result is the number that is missing from the array `nums`.

```csharp
public class Solution {
    public int MissingNumber(int[] nums) {
        
        int expectedSum=nums.Length*(nums.Length+1)/2;
        int actualSum=0;
        foreach(var num in nums)actualSum+=num;
        return expectedSum-actualSum;
        
    }
}
```

> Complexity

* **Time Complexity:** O(N)
* **Auxiliary Space:** O(1)