Day of the Programmer- HackerRank problem

 

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$.
If it is impossible to do so, print $-1$.

Constraints

• $1 \leq T \leq 500$
• $1 \leq N \leq 1000$
• $0 \leq A_i \leq 1000$

Sample 1:

Input

Output

4
4
3 1 1 2
3
0 3 3
3
3 2 1
3
2 0 1

3
-1
0
3

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.

CodeChef starters 69.

Solution:

It will be updated after a few times.