Elements Appearing More Than n/3 Times
mediumArrays & Prefix Sums+20 XPTime limit 2s
Find every value that appears more than n / 3 times (that is, 3 × count > n). There can be at most two such values — can you see why?
Input:
- line 1:
n - line 2:
nintegers
Output: the values in increasing order, separated by spaces — or -1 if there are none.
Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.
Think about it: a hash map works. For O(1) extra space, extend Boyer–Moore voting to two candidates: when a new value matches neither candidate and both counters are positive, decrease both. Finally verify the two candidates with a second pass — they are only possible answers.
Sample input 1
7 3 2 3 1 3 2 2
Sample output 1
2 3
Sample input 2
3 1 2 3
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).