# 1. Introduction

In this blog post, we discuss a commonly encountered problem in array manipulation: finding the majority element. The majority element is defined as the element that appears more than n/2 times in an array of size n. It's a fascinating problem that can be solved efficiently, demonstrating key concepts in algorithm design and data structure usage.

## Problem

Given an integer array nums of size n, the goal is to find and return the majority element. The majority element is the one that appears more than ⌊n / 2⌋ times. It is guaranteed that the majority element always exists in the array.

# 2. Solution Steps

1. Use the Boyer-Moore Voting Algorithm, which is an efficient method to find the majority element.

2. Initialize two variables: one to hold the potential majority element (candidate) and another for counting (count).

3. Traverse the array, updating candidate and count according to the Boyer-Moore logic.

4. The candidate at the end of the traversal will be the majority element.

# 3. Code Program

``````#include <stdio.h>

// Function to find the majority element in an array
int findMajorityElement(int* nums, int numsSize) {
int count = 0;
int candidate = 0;

// Iterating through the array
for (int i = 0; i < numsSize; i++) {
if (count == 0) {
candidate = nums[i];
}
count += (nums[i] == candidate) ? 1 : -1;
}

return candidate;
}

// Main function to test the findMajorityElement function
int main() {
int nums1[] = {3, 2, 3};
int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);
printf("Majority Element in [3,2,3]: %d\n", findMajorityElement(nums1, numsSize1));

int nums2[] = {2, 2, 1, 1, 1, 2, 2};
int numsSize2 = sizeof(nums2) / sizeof(nums2[0]);
printf("Majority Element in [2,2,1,1,1,2,2]: %d\n", findMajorityElement(nums2, numsSize2));

return 0;
}

``````

### Output:

```Majority Element in [3,2,3]: 3
Majority Element in [2,2,1,1,1,2,2]: 2
```

### Explanation:

1. int count = 0; int candidate = 0; - Initialize count and candidate.

2. for (int i = 0; i < numsSize; i++) - Iterate through the array.

3. if (count == 0) { candidate = nums[i]; } - If count is 0, take the current element as a new candidate.

4. count += (nums[i] == candidate) ? 1 : -1; - Increment count if the current element is the candidate, otherwise decrement.

5. return candidate; - The candidate at the end is the majority element.

6. In main, the function is tested with two example arrays and the majority elements are printed.