ナオヒロくんがいま持っている整数の最小値と最大値がわかれば、はじめ持っていた整数がすべてわかります。

最小値を \(A _ {\mathrm{min}}\) 、最大値を \(A _ {\mathrm{max}}\) とします。 長さ \(L=A _ {\mathrm{max}}-A _ {\mathrm{min}}+1(=N+1)\) の配列を使って、ナオヒロくんがはじめ持っていた整数のうちどの整数をいま持っているかを調べることができます。 この配列を順に調べることで、なくした整数が何であるかがわかります。

時間計算量は \(O(N)\) になります。 実装例は以下のようになります。

N = int(input()) # N を読み込む
*A, = map(int, input().split()) # A を読み込む

min_A = min(A) # A の最小値を計算

# 小さいほうから i 番目の整数を持っているか調べる (0 ≤ i ≤ N)
now_have = [False for i in range(N + 1)]

for a in A:
  # 整数 a は小さいほうから a - min_A 番目 (はじめが 0 )
  now_have[a - min_A] = True

for i in range(N + 1):
  if not now_have[i]: # 持っていない整数がなくした整数
    print(i + min_A)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N; // N を読み込む
    vector<int> A(N);
    for (auto &&a : A)
        cin >> a; // A を読み込む

    int min_A = ranges::min(A); // A の最小値を計算

    vector<bool> now_have(N, false); // 今持っている整数を調べる
    for (int a : A)
        now_have[a - min_A] = true; // a - min_A 番目は持っている

    for (int i = 0; i < N; ++i)
        if (!now_have[i]) // 持っていない整数がなくした整数
            cout << i + min_A << endl;
    
    return 0;
}