## Introduction

In this tutorial, we’ll explore the “Majority Element” interview question and provide a comprehensive solution using C++. The Majority Element is a common coding interview problem that tests your ability to find an element that appears more than n/2 times in an array of size n. We’ll walk through the problem statement, discuss different approaches to solving it, and implement the solution in C++.

## Problem Statement

You are given an array of integers, and you need to find the majority element. A majority element is an element that appears more than n/2 times in the array, where n is the size of the array. It is guaranteed that a majority element always exists in the array.

For example, consider the array:

`[3, 1, 3, 3, 2]`

In this case, the majority element is 3, as it appears three times, which is more than half of the total elements (5/2 = 2.5).

## Brute Force Approach

A straightforward approach to solving this problem is by using nested loops to count the occurrences of each element and finding the one that appears more than n/2 times. Here’s a step-by-step breakdown of this approach:

- Initialize a variable
`maxCount`

to keep track of the maximum count of an element. - Initialize a variable
`majorityElement`

to store the element that appears more than n/2 times. - Loop through each element
`num`

in the array.

- Initialize a variable
`count`

to 0. - Loop through the array again to count the occurrences of
`num`

. - If
`count`

is greater than`maxCount`

, update`maxCount`

and`majorityElement`

.

- After both loops,
`majorityElement`

will contain the majority element.

### Implementation

Here’s the implementation of the brute force approach in C++:

```
#include <iostream>
#include <vector>
int findMajorityElement(const std::vector<int>& nums) {
int n = nums.size();
int maxCount = 0;
int majorityElement = 0;
for (int num : nums) {
int count = 0;
for (int otherNum : nums) {
if (otherNum == num) {
count++;
}
}
if (count > maxCount) {
maxCount = count;
majorityElement = num;
}
}
return majorityElement;
}
int main() {
std::vector<int> nums = {3, 1, 3, 3, 2};
int majority = findMajorityElement(nums);
std::cout << "Majority Element: " << majority << std::endl;
return 0;
}
```

## Optimal Approach: Boyer-Moore Voting Algorithm

The brute force approach works, but it has a time complexity of O(n^2) due to the nested loops. We can achieve a more efficient solution using the Boyer-Moore Voting Algorithm, which has a time complexity of O(n) and a space complexity of O(1).

The key idea behind this algorithm is that if we cancel out each occurrence of an element `x`

with all the other elements that are different from `x`

, then `x`

will be the majority element if it indeed is a majority element.

Here’s a step-by-step breakdown of the Boyer-Moore Voting Algorithm:

- Initialize two variables
`candidate`

and`count`

to keep track of the current candidate for the majority element and its count, respectively. - Loop through each element
`num`

in the array.

- If
`count`

is 0, assign`num`

to`candidate`

and set`count`

to 1. - If
`num`

is the same as`candidate`

, increment`count`

; otherwise, decrement`count`

.

- After the loop, the
`candidate`

will contain the majority element. - To confirm that the
`candidate`

is the majority element, loop through the array again and count its occurrences.

- If the count of
`candidate`

is greater than n/2, return`candidate`

; otherwise, return -1 to indicate no majority element.

### Implementation

Here’s the implementation of the Boyer-Moore Voting Algorithm in C++:

```
#include <iostream>
#include <vector>
int findMajorityElement(const std::vector<int>& nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
// Confirm the candidate is the majority element
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
if (count > nums.size() / 2) {
return candidate;
} else {
return -1; // No majority element
}
}
int main() {
std::vector<int> nums = {3, 1, 3, 3, 2};
int majority = findMajorityElement(nums);
if (majority != -1) {
std::cout << "Majority Element: " << majority << std::endl;
} else {
std::cout << "No Majority Element" << std::endl;
}
return 0;
}
```

## Testing and Analysis

Let’s test our solution with various inputs to ensure its correctness and efficiency.

### Test Case 1

Input:

`[3, 1, 3, 3, 2]`

Output:

`Majority Element: 3`

### Test Case 2

Input:

`[1, 2, 2, 3, 2]`

Output:

`Majority Element: 2`

### Test Case 3

Input:

`[1, 2, 3, 4, 5]`

Output:

`No Majority Element`

## Conclusion

In this tutorial, we’ve covered the Majority Element interview question and provided a detailed solution in C++. We discussed both the brute force approach and the more efficient Boyer-Moore Voting Algorithm. By using the Boyer-Moore algorithm, we can solve the problem in O(n) time complexity and O(1) space complexity, making it a much more efficient solution. Remember to thoroughly test your code with different test cases to ensure its correctness and efficiency in various scenarios. Happy coding!