[Solution] Convert to permutation CodeChef Solution 2022

Problem

You are given an array $A$ of size $N$. In one operation, you can:

• Choose an index $i$ $(1\le i \le N)$ and increase $A_i$ by $1$.

Find the minimum number of operations required to convert the array $A$ into a permutation of size $N$. If it is impossible to do so, print $-1$.

Note that a permutation of size $N$ contains each element from $1$ to $N$ exactly once.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains the integer $N$ — the size of the array.
  • The next line contains $N$ space-separated integers, the elements of the array $A$.

Output Format

For each test case, output on a new line, the minimum number of operations required to convert the array $A$ into a permutation of size $N$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

If it is impossible to do so, print $-1$.

Explanation:

Test case $1$: We can convert the array $A$ into a permutation using $3$ operations:

• Operation $1$: Choose $i = 3$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 1, 2, 2]$.
• Operation $2$: Choose $i = 3$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 1, 3, 2]$.
• Operation $3$: Choose $i = 3$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 1, 4, 2]$.

It can be shown that this is the minimum number of operations required to convert $A$ into a permutation.

Test case $2$: The given array cannot be converted into a permutation using any number of operations.

Test case $3$: The given array is already a permutation. Thus, we require $0$ operations.

Test case $4$: We can convert the array $A$ into a permutation using $3$ operations:

• Operation $1$: Choose $i = 1$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 0, 1]$.
• Operation $2$: Choose $i = 2$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 1, 1]$.
• Operation $3$: Choose $i = 3$ and increase $A_i$ by $1$. Thus, the array becomes $A = [3, 1, 2]$.

It can be shown that this is the minimum number of operations required to convert $A$ into a permutation.