One can check if each of \(1, 2, 3, \dots, N\) as an element of \(A\) to solve in a total of \(O(N)\) time time.

Sample code (C++)

Otherwise, one can sort the elements of \(A\) in the increasing order and check if \(1, 2, \dots, N\) are in this order to solve in a total of \(O (N \log N)\) time.

Sample code (C++)

Sample code (Python)