# 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;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://twchen.gitbook.io/leetcode/array/find-all-numbers-disappeared-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.