\(A\) の要素として \(1, 2, 3, \dots, N\) が全て現れるかどうか調べることで、 \(O(N)\) で解くことができます。

実装例 (C++)

あるいは、\(A\) の要素を昇順に並べたときに \(1, 2, \dots, N\) がこの順に並んでいるかどうか調べることで、\(O (N \log N)\) で解くことができます。

実装例 (C++)

実装例 (Python)