Contest: Division 1
Contest: Division 2

Setter: Jafar Badour
Tester: Hussain
Editorialist: Taranpreet Singh




Observation would be enough.


Given array A of N numbers, Change this array to a permutation of [1,N] in minimum number of steps.

In each step, we can change one number at any position to any number.


  •   Minimum number of moves is same as $N$ less Number of distinct elements in range $[1,N]$ present in $A$.


Let us consider example where A doesn’t contain any element in range [1,N]. Then, to obtain a permutation of [1,N], we need to change all elements on array exactly once, to obtain permutation, resulting in N moves.

So, we are guaranteed to get permutation in at most N moves. But we seek minimum number of moves.

Now, If there are any elements in range [1,N] already present in array, we can just keep them as it is, reducing number of steps performed. So, If we can keep x elements from original array, The number of operations to be performed becomes N - x. So, Our aim is to maximize x, that is, Keep as many elements from original array. But, we can keep only one occurrence of each number in range [1,N]. So, if there are x distinct numbers in range [1,N] present in given array, Minimum number of steps is N-x.

Consider example N = 8, A = 3 10 11 12 13 1 2 3

About duplicates, consider example A = 3 10 11 12 13 1 2 3. we know that in a permutation, every element is present exactly once, so, Having more than one occurrence of a number, is useless, since we will have to remove it. So, Only distinct occurrences of elements in range [1,N] matters.

So, our Answer becomes N less Distinct elements in range [1,N] present in A.

Quite short editorial, but that’s all the problem had.

Time Complexity

O(N) per test case.


Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: