# Find the Majority Element that occurs more than N/2 times

[Question] Find the Majority Element in an given array that occurs more than N/2 times

###### Approach #1 Brute-force

Use two loop and compare each elements with rest if it matches increment the counter

``````// TC: O(n*2)
// SC: O(1)
func majorityElement(arr: inout [Int]) -> Int {
// Size of the given array
let n = arr.count

for i in 0..<n {
// Selected element is arr[i]
var cnt = 0
for j in 0..<n {
// Counting the frequency of arr[i]
if arr[j] == arr[i] {
cnt+=1
}
}

// Check if frequency is greater than n/2
if (cnt > n/2) {
return arr[i]
}
}

return -1
}``````
###### Approach #2 : Optimal Approach: Moore’s Voting Algorithm

Basically, we are trying to keep track of the occurrences of the majority element and minority elements dynamically. if the count becomes 0 as the occurrence of Element and the occurrence of the other elements are the same. So, they canceled each other. The element with the most occurrence will remain and the rest will cancel themselves.

``````func majorityElementMooreVoting(arr: inout [Int]) -> Int {
// Size of the given array
let n = arr.count
var cnt = 0 // Count
var el = 0 // Element

// Applying the algorithm
for i in 0..<n {
if cnt == 0 {
cnt = 1
el = arr[i]
} else if el == arr[i] {
cnt+=1
} else {
cnt-=1
}
}

// Checking if the stored element is the majority element
var cnt1 = 0
for i in 0..<n where arr[i] == el {
cnt1+=1
}

if (cnt1 > n / 2) {
return el
}
return -1
}``````
``````var majorityArr = [2, 2, 1, 1, 1, 2, 2]
let ansMajority = majorityElementMooreVoting(arr: &majorityArr)
print("The majority element is:", ansMajority)``````