CA 21 - Find the Majority Element

Problem
Find the Majority Element
You are given an array arr[].
Your task is to find the majority element in the array.

A majority element is one that appears more than n/2 times.
If no such element exists, return -1.

Input: [1, 1, 2, 1, 3, 5, 1] → Output: 1
Input: [7] → Output: 7
Input: [2, 13] → Output: -1

Approach

We use the Boyer-Moore Voting Algorithm, which finds a potential majority element in one pass
After this pass, we verify if the candidate actually appears more than n/2 times.

Steps:

• Initialize candidate and count = 0
• Traverse the array:
• If count is 0 → set current element as candidate
• If element equals candidate → increment count
• Else → decrement count
• Verify the candidate by counting its occurrences

Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

def majorityElement(arr):
    candidate = None
    count = 0
    for num in arr:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    if arr.count(candidate) > len(arr) // 2:
        return candidate
    else:
        return -1
arr = [1, 1, 2, 1, 3, 5, 1]
print(majorityElement(arr))