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. 