Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.