Solution 1: Implement in the Manner of Packet Sort

The problem can be solved in the manner of bucket sort.

Prepare an array initialized with \(bucket[x]=0\), and set \(bucket[x]=1\) when you find a value \(x\) in \(A\).
Then, for each \(i=1,2,\dots,N\), if \(bucket[i]=0\), then mark \(i\) as one of the sought integers.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> bk(n+1,0);
  for(int i=0;i<m;i++){
    int a;
    cin >> a;
    bk[a]=1;
  }
  vector<int> res;
  for(int i=1;i<=n;i++){
    if(bk[i]==0){
      res.push_back(i);
    }
  }
  cout << res.size() << "\n";
  for(int i=0;i<res.size();i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}

Solution 2: Sort \(A\) to Find the Answer

The problem can be solved by sorting \(A\) and doing the following:

• Let \(p = 1\).
• For each \(i = 1,2,\dots,N\), do the following.
  • If \(p \le M\) and \(A_p = i\), add \(1\) to \(p\).
  • Otherwise, mark \(i\) as one of the sought integers.

For example, if \(N=6, M=3\), and \(A=(1,2,5)\), it runs as follows:

• Let \(p=1\).
• For \(i=1\), we have \(A_p = A_1 = 1\), so let \(p\) be \(2\).
• For \(i=2\), we have \(A_p = A_2 = 2\), so let \(p\) be \(3\).
• For \(i=3\), we have \(A_p = A_3 = 5 \neq 3\), so mark \(3\) as one of the sought integers.
• For \(i=4\), we have \(A_p = A_3 = 5 \neq 4\), so mark \(4\) as one of the sought integers.
• For \(i=5\), we have \(A_p = A_3 = 5\), so let \(p\) be \(4\).
• For \(i=6\), we have \(p = 4 > M = 3\), so mark \(6\) as one of the sought integers.

This solution works because the elements of \(A\) are pairwise distinct. If \(A\) has repeated values, the solution needs modified.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m);
  for(auto &nx : a){cin >> nx;}
  sort(a.begin(),a.end());
  int p=0;
  vector<int> res;
  for(int i=1;i<=n;i++){
    if(p>m){res.push_back(i);}
    else if(a[p]!=i){res.push_back(i);}
    else{p++;}
  }
  cout << res.size() << "\n";
  for(int i=0;i<res.size();i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}