 # MAKPERM - EDITORIAL

Tester: Hussain
Editorialist: Taranpreet Singh

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:

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