## Editorial for DMOPC '20 Contest 3 P1 - Present Checking

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

The problem is asking if the input array is a permutation of the integers from to .

#### Subtask 1

For the first subtask, we can naively check if each number from to is present in the array. Because such a check takes time, this solution runs in .

**Time Complexity**:

#### Subtask 2

There are many ways that we can check this efficiently:

We can use an array of size to track the number of times each element appears, and then ensure that they each appear once exactly.

We can use a set to track the elements we've seen before.

We can sort the array, and ensure that adjacent elements are not equal. This is sufficient because each element in the input is between and , so checking that they are all distinct is equivalent.

**Time Complexity**: or

## Comments