C. Pokedex

3.5

8 votes
Medium
Problem

Sonali and Priyanka are friends. Both are fascinated about "PokemonGo". One day Sonali give an Array to Priyanka and asks her to convert the Array into "Pokedex". A "Pokedex" is an Array such that all distinct elements in the Array occurs the same number of times in it. For example, A={1,1,2,2} is a "Pokedex" because both the numbers (1 and 2) occurs the same number of times. Whereas B={1,2,1,2,3} is NOT a "Pokedex" because the distinct elements (1,2,3) does not occurs the same number of time. Priyanka gives the Array to her bff Harshit and asks him to remove some elements from the Array, Such that the new Array results in a "Pokedex". Harshit wants to know from you if it's possible to be done with less then or equals to one removal.

Input Format:
First line contains a integer T that represents the total no. of test cases.
Each test case follows with a integer N the size of the array.
Next line contains N space separated integers.

Output Format:
For each testcase, print "YES" if there is a possibility to make the array a "Pokedex", Else print "NO".

Constraints:
1<=t<=10
1<=n<=10^5
1<=Array element <=10^7

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

In the first test case (1,2,3) occurs the same number of times so its already a Pokedex.
In second case we would need more then one removals to form a Pokedex.

Editor Image

?