PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
1126
PREREQUISITES:
None
PROBLEM:
A pet store has N types of animals, the i-th of which has type A_i.
Alice will buy some of these animals and Bob will buy the rest. Is there a way for them to end up with exactly the same multiset of types of animals?
EXPLANATION:
Each type of animal bought by Alice must have a copy that she didn’t buy, so that Bob can buy this copy.
In other words, for a valid split to exist, every type of animal must be present an even number of times.
It’s easy to see that this condition is both necessary and sufficient.
So, all that needs to be done is to check whether each type of animal occurs an even number of times.
One way to do that is as follows:
- Create an array c of length 100, where c_x denotes the number of times x occurs in A.
- This is easy to do in \mathcal{O}(N), by simply iterating i from 1 to N and incrementing c_{A_i} by 1 each time.
- Then, check whether every c_x is even.
Alternately, you can also sort A and check whether A_{2i-1} = A_{2i} (in 1-indexing) for every i.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Code (Python)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 'Yes' if n%2 == 0 else 'No'
for i in range(1, n, 2):
if a[i] != a[i-1]: ans = 'No'
print(ans)