# Missing Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/missing-number)
Canonical: https://scaleengineer.com/dsa/problems/missing-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Nvidia](https://scaleengineer.com/companies/nvidia), [tcs](https://scaleengineer.com/companies/tcs), [Tesla](https://scaleengineer.com/companies/tesla), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [Revolut](https://scaleengineer.com/companies/revolut), [AQR Capital Management](https://scaleengineer.com/companies/aqr-capital-management), [Genpact](https://scaleengineer.com/companies/genpact)
---
## Problem
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:**

**Input:** nums = \[3,0,1\]

**Output:** 2

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

**Example 2:**

**Input:** nums = \[0,1\]

**Output:** 2

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

**Example 3:**

**Input:** nums = \[9,6,4,2,3,5,7,0,1\]

**Output:** 8

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

**Constraints:**

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

**Follow up:** Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?

# Approaches
## Brute Force - Linear Search
Check each number from 0 to n if it exists in the array. The first number that is not found in the array is the missing number.
**Time:** O(n²) - For each number from 0 to n, we search the entire array · **Space:** O(1) - Only using constant extra space
**Pros:** Simple to understand and implement; No extra space required
**Cons:** Very inefficient for large arrays; Requires nested loops
### Explanation
This approach involves iterating through each number from 0 to n and for each number, we search the entire array to check if it exists. If a number is not found in the array, that is our missing number.

```java
public int missingNumber(int[] nums) {
    int n = nums.length;
    for (int i = 0; i <= n; i++) {
        boolean found = false;
        for (int j = 0; j < n; j++) {
            if (nums[j] == i) {
                found = true;
                break;
            }
        }
        if (!found) {
            return i;
        }
    }
    return -1;
}
```
### Algorithm
1. For each number i from 0 to n:
   - Search for i in the array nums
   - If i is not found, return i

## Sorting Based Approach
Sort the array first and then check for the first missing number by comparing adjacent elements.
**Time:** O(n log n) - Dominated by the sorting operation · **Space:** O(1) - Only using constant extra space
**Pros:** Easy to understand; No extra space needed (if using in-place sorting); Works well for small arrays
**Cons:** Modifies the original array; Not as efficient as other solutions; Sorting is expensive
### Explanation
First, we sort the array in ascending order. Then we iterate through the sorted array and check if each number is equal to its index. The first position where this condition fails is our missing number. If we reach the end without finding a mismatch, then n is the missing number.

```java
public int missingNumber(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    
    // Check if n is missing
    if (nums[n-1] != n) {
        return n;
    }
    // Check if 0 is missing
    if (nums[0] != 0) {
        return 0;
    }
    
    for (int i = 1; i < n; i++) {
        int expectedNum = nums[i-1] + 1;
        if (nums[i] != expectedNum) {
            return expectedNum;
        }
    }
    return -1;
}
```
### Algorithm
1. Sort the array in ascending order
2. If first element is not 0, return 0
3. If last element is not n, return n
4. Iterate through sorted array checking for gaps between consecutive numbers
5. Return the first gap found

## HashSet Approach
Use a HashSet to store all numbers from the array, then find the missing number by checking which number from 0 to n is not in the set.
**Time:** O(n) - We traverse the array once to build the set and once to find the missing number · **Space:** O(n) - We store all numbers in a HashSet
**Pros:** O(n) time complexity; Easy to implement; Does not modify original array
**Cons:** Requires extra space; Not as space efficient as other solutions
### Explanation
We first create a HashSet and add all numbers from the array to it. Then we iterate from 0 to n and check which number is not present in the set. That number is our missing number.

```java
public int missingNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int n = nums.length;
    
    // Add all numbers to set
    for (int num : nums) {
        set.add(num);
    }
    
    // Find missing number
    for (int i = 0; i <= n; i++) {
        if (!set.contains(i)) {
            return i;
        }
    }
    return -1;
}
```
### Algorithm
1. Create a HashSet
2. Add all numbers from array to HashSet
3. Check each number from 0 to n
4. Return first number not found in HashSet

## Mathematical Approach (Sum Formula)
Use the formula for sum of first n natural numbers and subtract the sum of array elements to find the missing number.
**Time:** O(n) - We only need to traverse the array once to calculate the sum · **Space:** O(1) - Only using constant extra space
**Pros:** O(n) time complexity; O(1) space complexity; Simple and elegant solution; Does not modify original array
**Cons:** Might have integer overflow for large values; Not as intuitive as other approaches
### Explanation
We can find the missing number by calculating the difference between the expected sum of numbers from 0 to n and the actual sum of numbers in the array. The expected sum can be calculated using the formula n*(n+1)/2.

```java
public int missingNumber(int[] nums) {
    int n = nums.length;
    int expectedSum = (n * (n + 1)) / 2;
    int actualSum = 0;
    
    for (int num : nums) {
        actualSum += num;
    }
    
    return expectedSum - actualSum;
}
```
### Algorithm
1. Calculate expected sum using formula: n*(n+1)/2
2. Calculate actual sum of array elements
3. Return the difference between expected and actual sum

## XOR Approach
Use XOR operation to find the missing number by exploiting the properties of XOR operation.
**Time:** O(n) - We only need to traverse the array once · **Space:** O(1) - Only using constant extra space
**Pros:** O(n) time complexity; O(1) space complexity; No risk of integer overflow; Most efficient solution; Does not modify original array
**Cons:** Not as intuitive as other approaches; Requires understanding of XOR properties
### Explanation
We can use XOR operation to find the missing number. XOR all numbers from 0 to n with all numbers in the array. Due to XOR properties (a^a=0 and a^0=a), all numbers except the missing one will be cancelled out.

```java
public int missingNumber(int[] nums) {
    int n = nums.length;
    int result = n;
    
    for (int i = 0; i < n; i++) {
        result ^= i ^ nums[i];
    }
    
    return result;
}
```
### Algorithm
1. Initialize result with n
2. XOR result with each index and value in array
3. Return result which will be the missing number

# Solutions
### Java

```java
class Solution {
public
  int missingNumber(int[] nums) {
    int n = nums.length;
    int ans = n;
    for (int i = 0; i < n; ++i) {
      ans ^= (i ^ nums[i]);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var missingNumber =
  function (nums) {
    const n = nums.length;
    let ans = n;
    for (let i = 0; i < n; ++i) {
      ans ^= i ^ nums[i];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int missingNumber(vector<int> &nums) {
    int n = nums.size();
    int ans = n;
    for (int i = 0; i < n; ++i) {
      ans ^= (i ^ nums[i]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def missingNumber(
        self, nums: List[int]) -> int: return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))

```