Majority Element - C Solution

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.