314. Appearing More Than a Third of the Time
Core1000 ms256 MBSolved by 0%
Print every value appearing STRICTLY more than n / 3 times, in increasing
order. Print None if there is no such value.
There can be at most two such values, because three of them would each need more than a third and together exceed the whole array. That is worth working out before writing anything, since it tells you the answer is tiny however large the input is.
Compare with count * 3 > n rather than count > n / 3. Integer division
truncates, so the second form accepts a value that appears exactly a third of
the time when n is divisible by 3.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print the qualifying values in increasing order separated by single spaces, or None.
Input3
3 2 3
Output3
Notehas one value appearing twice out of three
Input3
1 2 3
OutputNone
Notehas every value at exactly a third, which does not qualify
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution