# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Abhinav Gupta

Tester: Satyam, Tejas Pandey

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1737

# PREREQUISITES:

None

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

# EXPLANATION:

Suppose in the array there are distinct elements A_1,A_2â€¦A_n, with frequencies f_1,f_2,...,f_n. Then for each element A_i, we will proceed as follows:

Case \;1: f_i = 1

In this case the number is already distinct, so no operation is required.

Case \; 2: f_i > 1

In this case we will select half of elements of A_i and increase it by an arbitrary high number.

We can do the operations for all the distinct elements at the same time.

So in each operation, we will select all the distinct elements A_i, such that f_i > 1 and increase half of the elements to a arbitrary higher value.

Thus in all we just have to calculate the maximum f_i, say f_{max} and in each operation we will reduce the frequency f_{max} by half, thus our answer would be

Since operations would be applied to all f_j < f_{max}, at the same time so we just have to calculate for maximum f_i.

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution