Educatifu
Open menu

Majority Element

Mediumarrays

Find the element that appears more than n/2 times in an array. Such an element is guaranteed to exist.

Input

Line 1: an integer n. Line 2: n integers.

Output

The majority element.

Examples

Example 1

Input
3
3 2 3
Output
3

3 appears twice of three — a majority.

Example 2

Input
7
2 2 1 1 1 2 2
Output
2

2 appears four of seven times.

Example 3

Input
1
5
Output
5

The only element is the majority.

Constraints

  • 1 <= n <= 10^5
  • A majority element (count > n/2) always exists.

Hints

Reveal hint 1

Counting every value works, but there is a clever O(1)-space way.

Reveal hint 2

Boyer–Moore voting: keep a candidate and a counter; on a match increment, otherwise decrement, and reset the candidate when the counter hits 0.

Reference solution (spoiler — try it yourself first)

Approach

Boyer–Moore majority vote: because the majority element outnumbers all others combined, its net vote survives.

import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
a = d[1:1 + n]
cand = None
cnt = 0
for x in a:
    if cnt == 0:
        cand = x
    cnt += 1 if x == cand else -1
print(cand)

← All practice problems

Bring us the problem, not a perfect specification

Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.

  1. 01Share contextDescribe the workflow, constraint or risk.
  2. 02Clarify togetherWe identify missing facts and useful options.
  3. 03Choose a startAgree a focused assessment or delivery step.
Start a conversation