# 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.

### Constraints

• 1 \leq T \leq 4000
• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• Sum of N over all test cases do not exceed 3 \cdot 10^5

### Sample 1:

Input

Output

4
3
3 3 3
6
1 3 2 1 2 2
4
1 2 1 2
5
1 3 2 4 6

2
2
1
0


### 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.

## Add to Subsequence Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW