Skip to main content

Additional

Boyer-Moore Majority Voting Algorithm​

Majority element

def findMajority(arr):
    N = len(arr)
    # finding the majority
    res = 0
    count = 1
    for i in range(1, N):
        if arr[res] == arr[i]:
            count += 1
        else:
            count -= 1
        if count == 0:
            res = i
            count = 1
    # verifying the majority
    count = 0
    for i in range(N):
        if arr[res] == arr[i]:
            count += 1
    if count <= N // 2:
        res = -1
    return res