1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
# Uses python3
import sys
def getMajorityElement(a, left, right):
if left == right:
return a[left]
middle = (int) ((right - left) / 2)
b = getMajorityElement(a, left, left + middle)
c = getMajorityElement(a, left + middle + 1, right)
d = conquer(a[left:right + 1], b, c)
return d
def conquer(a, b, c):
countB = 0
countC = 0
for i in a:
if i == b:
countB = countB + 1
if i == c:
countC = countC + 1
if countB > (len(a) / 2):
return b;
if countC > (len(a) / 2):
return c
return -1
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
if getMajorityElement(a, 0, n - 1) != -1:
print(1)
else:
print(0)
|
