> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/array/find-all-numbers-disappeared-in-an-array.md).

# Find All Numbers Disappeared in an Array

## Description

Given an array of integers where 1 ≤ a\[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of \[1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

**Example:**

```
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
```

## Solutions

### My solution

```cpp
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        while(i < n){
            if(nums[i] == i + 1 || nums[nums[i] - 1] == nums[i]){
                ++i;
            }else{
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        vector<int> ans;
        for(int j = 0; j < n; ++j){
            if(nums[j] != j + 1)
                ans.push_back(j + 1);
        }
        return ans;
    }
};
```

The running time is O(n). Proof:

We say that a number `nums[i]` is at its correct position if `nums[i] == i + 1`. After each `swap` statement, at least one number, i.e., `nums[i]`, is put to its correct position. Since we can put at most n numbers to their correct positions and once a number is put to its correct position, it no longer moves. Thus, the `swap` statement is executed at most n times. And the `++i` statement is also executed at most n times. So the running time of the while loop is O(n). The remaining is trivial.

### A better solution

This solution is more efficient, though the time complexity is the same. It also modifies the input array, but the modification can be revert.

**The idea to mark the numbers that appears in the array with negative values**. Another similar idea is to mark these numbers by adding `n`(but overflow may occur).

```cpp
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        // nums[i] < 0 <=> i+1 is in the array
        for(int i = 0; i < n; ++i){
            int idx = abs(nums[i]) - 1;
            if(nums[idx] > 0)
                nums[idx] = -nums[idx];
        }
        vector<int> ans;
        for(int i = 0; i < n; ++i){
            if(nums[i] > 0)
                ans.push_back(i + 1);
        }
        return ans;
    }
};
```