Annihilator Gun (Editoryal)

Let's analyze three cases:

1. When all the numbers in the array are the same.

2. When the number of distinct numbers in the array is more than $1$ but less than $k$.

3. When there are exactly $k$ distinct numbers.

1) If all the numbers in the array are already the same, the answer is $0$.

2) When the number of distinct numbers in the array is $<k$.

Then there exists a number $X$ that is not in the array, and 1 \le X \le k.

In this case, we can change the types of all planets to $X$.

The answer is $1$.

3) There are two cases:

3.1) k == 2

If we apply the operation, we can replace all 1s with 2s and all 2s with 1s.

Therefore, it will never happen that all the numbers in the array are equal.

3.2) k > 2

It is easy to show that the answer can neither be $0$ nor $1$.

We can show that the answer will always be $2$.

Let the first operation replace all non-1s with 1, and all 1s with 2. In the second operation, we can replace all the numbers with 3.

Full solution with O(nlogn) time complexity (C++):

int n, k;
cin >> n >> k;
 
vector <int> a(n);
 
set <int> s;
 
for (int i = 0; i < n; i++)
{
	cin >> a[i];
 
	s.insert(a[i]);
}
 
if (s.size() == 1)
{
	cout << 0;
	return 0;
}
if ((s.size() == k) and (k == 2))
{
	cout << -1;
	return 0;
}
 
if ((s.size() == k))
{
	cout << 2;
	return 0;
}
 
cout << 1;

Time complexity: O(nlogn) or $O(n)$

Memory complexity: $O(n)$