MAKPERM - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Jafar Badour
Tester: Hussain
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Observation would be enough.

PROBLEM:

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.

SUPER QUICK EXPLANATION

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

EXPLANATION

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

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

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

//