Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Majority Element

Medium · Arrays · Asked at Amazon, Microsoft, Google, Adobe

Find the element that appears more than n/2 times. Such an element always exists.

Input

First line: n. Second line: n space-separated integers.

Output

The majority element.

Constraints

Moore's Voting Algorithm does it in O(n) time and O(1) space.

Example 1

Input

3
3 2 3

Output

3

Example 2

Input

7
2 2 1 1 1 2 2

Output

2

Hints

  1. A hash map of counts works in O(n) space. Can you do it in O(1)?
  2. Moore's voting: keep a candidate and a counter; equal values add a vote, different values remove one.

Approach

Moore's voting algorithm pairs off different values against each other. Keep candidate and count: when count is 0, adopt the current value; same value → count++, different → count--. The majority element appears more than n/2 times, so it can't be fully cancelled and is the final candidate.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long candidate = 0, x;
    int count = 0;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (count == 0) candidate = x;
        count += (x == candidate) ? 1 : -1;
    }
    cout << candidate << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
candidate, count = 0, 0
for x in data[1 : data[0] + 1]:
    if count == 0:
        candidate = x
    count += 1 if x == candidate else -1
print(candidate)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), count = 0;
        long candidate = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (count == 0) candidate = x;
            count += (x == candidate) ? 1 : -1;
        }
        System.out.println(candidate);
    }
}

Solve Majority Element online · All practice problems