Algorithmic Toolbox : Majority Element Problem (WEEK 4)

 Majority Element



#  Majority Element
# Problem Introduction
# Majority rule is a decision rule that selects the alternative which has a majority,
# that is, more than half the votes.
# Given a sequence of elements 𝑎1, 𝑎2, . . . , 𝑎𝑛, you would like to check whether
# it contains an element that appears more than 𝑛/2 times. A naive way to do
# this is the following.
# MajorityElement(𝑎1, 𝑎2, . . . , 𝑎𝑛):
# for 𝑖 from 1 to 𝑛:
# currentElement ← 𝑎𝑖
# count ← 0
# for 𝑗 from 1 to 𝑛:
# if 𝑎𝑗 = currentElement:
# count ← count + 1
# if count > 𝑛/2:
# return 𝑎𝑖
# return “no majority element”
# The running time of this algorithm is quadratic. Your goal is to use the divide-and-conquer technique to
# design an 𝑂(𝑛 log 𝑛) algorithm.
# 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 𝑛, the next one contains a sequence of 𝑛 non-negative
# integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1.
# Constraints. 1 ≤ 𝑛 ≤ 105
# ; 0 ≤ 𝑎𝑖 ≤ 109
# for all 0 ≤ 𝑖 < 𝑛.
# Output Format. Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times,
# and 0 otherwise.
# Sample 1.
# Input:
# 5
# 2 3 9 2 2
# Output:
# 1
# 2 is the majority element.
# Sample 2.
# Input:
# 4
# 1 2 3 4
# Output:
# 0
# There is no majority element in this sequence.

# --------------------------Solution--------------------------------- 
# Majority Element 
n = int(input())
sequence = [int(i) for i in input().split()] #input sequence

def func(sequencelr):
    if l+1==r:
        return sequence[l]
    elif l+2==r:
        return sequence[l]
    m = (l+r)//2
    _left = func(sequence, l, m)
    _right = func(sequence, m, r)

    c1, c2 = 00
    for i in sequence[l:r]:
        if i == _left:
            c1+=1
        elif i == _right:
            c2+=1
    if c1>(r-l)//2 and _left != -1:
        return _left
    elif c2>(r-l)//2 and _right != -1:
        return _right
    else
        return -1

print(int(func(sequence, 0, n) != -1))