Problem Introduction
An element of a sequence of length \(n\) is called a majority element if it appears in the sequence strictly more than \(n/2\) times.
Problem Description
Task.The goal in this code problem is to check whether an input sequence contains a majority element.
Input Format.The first line contains an integer \(n\), the next one contains a sequence of \(n\) non-negative integers \(a_0,a_1,\cdots,a_{n-1}\).
Constraints.\(1 \leq n \leq 10^5; 0 \leq a_i \leq 10^9\) for all \(0 \leq i < n\).
Output Format.Ouput 1 if the sequence contains a majority element and 0 otherwise.
Sample 1.
Input:
5
2 3 9 2 2
Output:
1
Sample 2.
Input:
4
1 2 3 4
Output:
0
Sample 3.
Input:
4
1 2 3 1
Output:
0
Solution
# Uses python3
import sys
def get_majority_element(a, left, right):
if left == right:
return -1
if left + 1 == right:
return a[left]
mid = left + (right - left) // 2
majority_left = get_majority_element(a, left, mid)
majority_right = get_majority_element(a, mid, right)
b = a[left:right]
threshold = len(b) // 2
if b.count(majority_left) > threshold:
return majority_left
if b.count(majority_right) > threshold:
return majority_right
return -1
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
if get_majority_element(a, 0, n) != -1:
print(1)
else:
print(0)