[Solution] Add to Subsequence CodeChef Solution

Problem

Chef has an array $A$ of length $N$.

In one operation, Chef can choose any subsequence of the array and any integer $X$ and then add $X$ to all the elements of the chosen subsequence.

Determine the minimum number of operations required to make all the elements of the array distinct.

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 a single integer $N$ — the length of Array $A$.
  • Next line contains $N$ space-separated integers $A_1, A_2, A_3, \dots, A_N$ - denoting the array $A$.

Output Format

For each test case, output the minimum number of operations required to make all the elements distinct.

Explanation:

Test case $1$:

• Operation $1$: Choose the subsequence $\{A_1\}$ and add $X = 1$ to the elements. The array becomes $A = [4, 3, 3]$.
• Operation $2$: Choose the subsequence $\{A_2\}$ and add $X = 2$ to the elements. The array becomes $A = [4, 5, 3]$.

Thus, we require, minimum $2$ operations to make all the elements distinct.

Test case $2$:

• Operation $1$: Choose the subsequence $\{A_1, A_6\}$ and add $X = 4$ to the elements. The array becomes $A = [5, 3, 2, 1, 2, 6]$.
• Operation $2$: Choose the subsequence $\{A_3\}$ and add $X = 5$ to the elements. The array becomes $A = [5, 3, 7, 1, 2, 6]$.

Thus, we require, minimum $2$ operations to make all the elements distinct.

Test case $3$:

• Operation $1$: Choose the subsequence $\{A_3, A_4\}$ and add $X = 2$ to the elements. The array becomes $A = [1, 2, 3, 4]$.

Thus, we require, minimum $1$ operation to make all the elements distinct.

Test case $4$: All the elements are distinct. We need zero operations.