Find the Majority Element

Problem Statement

Given an array of size n, find the majority element.
The majority element is the element that appears more than n divided by 2 times.

You can assume that the majority element always exists in the array.

---

Examples

Input
arr = [3, 2, 3]

Output
3

---

Input
arr = [2, 2, 1, 1, 1, 2, 2]

Output
2

---

Approach 1 Using Counting

Count the frequency of each element and return the one with highest count.

---

Code

```python id="maj1"
def majorityElement(arr):
count = {}

for num in arr:
    count[num] = count.get(num, 0) + 1

n = len(arr)

for key in count:
    if count[key] > n // 2:
        return key

---

## Approach 2 Boyer Moore Voting Algorithm

This is the most efficient approach.

---

### Steps

1 Initialize count as 0 and candidate as None
2 Traverse the array
3 If count is 0 set current element as candidate
4 If element equals candidate increase count
5 Else decrease count

---

### Code



```python id="maj2"
def majorityElement(arr):
    count = 0
    candidate = None

    for num in arr:
        if count == 0:
            candidate = num

        if num == candidate:
            count += 1
        else:
            count -= 1

    return candidate

---

Explanation

The Boyer Moore algorithm works by canceling out different elements. The majority element will remain at the end because it appears more than half of the time.

---

Expected Output

Input
arr = [2, 2, 1, 1, 1, 2, 2]

Output
2

---

Conclusion

Finding the majority element is a common problem that helps in understanding frequency counting and optimization techniques. The Boyer Moore method is widely used because of its efficiency.

Practice this problem to improve your problem solving skills.