Majority Element Moore's Voting Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Moore's Voting Algorithm on given array

What is the output of the following C code that implements Moore's Voting Algorithm to find the majority element?

DSA C

#include <stdio.h>

int findMajority(int arr[], int size) {
    int count = 0, candidate = -1;
    for (int i = 0; i < size; i++) {
        if (count == 0) {
            candidate = arr[i];
            count = 1;
        } else if (arr[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

int main() {
    int arr[] = {2, 2, 1, 1, 1, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int majority = findMajority(arr, size);
    printf("%d\n", majority);
    return 0;
}

A 2

B 1

C 0

D No majority element

💡 Hint

Remember Moore's Voting Algorithm finds the candidate that may be the majority element by counting occurrences.

The algorithm selects 2 as the candidate because it appears more than half the time in the array (4 out of 7).

❓ Predict Output

intermediate

Output when no majority element exists

What will the following C code print when the input array has no majority element?

DSA C

#include <stdio.h>

int findMajority(int arr[], int size) {
    int count = 0, candidate = -1;
    for (int i = 0; i < size; i++) {
        if (count == 0) {
            candidate = arr[i];
            count = 1;
        } else if (arr[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    // Verify candidate
    count = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == candidate) count++;
    }
    if (count > size / 2) return candidate;
    else return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int majority = findMajority(arr, size);
    printf("%d\n", majority);
    return 0;
}

A -1

B 1

C 5

D 0

💡 Hint

The code verifies if the candidate appears more than half the time before returning it.

No element appears more than half the time, so the function returns -1.

🧠 Conceptual

advanced

Why Moore's Voting Algorithm works

Which of the following best explains why Moore's Voting Algorithm correctly finds the majority element?

A Because it sorts the array and picks the middle element.

B Because it uses recursion to divide and conquer the array.

C Because it counts the frequency of all elements using extra space.

D Because it cancels out pairs of different elements, leaving the majority element as the candidate.

💡 Hint

Think about how the algorithm reduces the count when encountering different elements.

The algorithm cancels out pairs of different elements, so the majority element remains as the candidate at the end.

🔧 Debug

advanced

Identify the bug in Moore's Voting Algorithm implementation

What is the bug in the following C code implementing Moore's Voting Algorithm?

DSA C

#include <stdio.h>

int findMajority(int arr[], int size) {
    int count = 0, candidate = 0;
    for (int i = 0; i < size; i++) {
        if (count == 0) {
            candidate = arr[i];
            count = 1;
        } else if (arr[i] != candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

int main() {
    int arr[] = {3, 3, 4, 2, 4, 4, 2, 4, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int majority = findMajority(arr, size);
    printf("%d\n", majority);
    return 0;
}

A The candidate is not initialized to -1.

B The count increments when element is different instead of decrementing.

C The array size calculation is incorrect.

D The function does not verify the candidate after selection.

💡 Hint

Check the condition that changes the count variable inside the loop.

The count should decrease when the current element is different from the candidate, but here it increases incorrectly.

🚀 Application

expert

Majority Element in a Stream of Data

You receive a stream of integers one by one and want to find the majority element at any point using Moore's Voting Algorithm. Which approach below correctly maintains the majority candidate and count as new elements arrive?

A Store all elements in an array and run Moore's Voting Algorithm from scratch after each new element.

B Initialize candidate to -1 and count to 0. For each new element, always increment count and update candidate to the new element.

C Initialize candidate and count to 0. For each new element, if count is 0, set candidate to element and count to 1; else if element equals candidate, increment count; else decrement count.

D Use a hash map to count frequencies and update candidate when a frequency exceeds half the total elements.

💡 Hint

Moore's Voting Algorithm can be adapted to streams by updating candidate and count incrementally.

Option C correctly describes the incremental update of candidate and count for streaming data.