</>EmbeddedInterview

How do you find the majority element (appearing more than n/2 times)?

MediumArrays & Strings (Coding Round)

Short answer: Use the Boyer–Moore voting algorithm: keep a candidate and a counter. For each element, if the counter is 0, take it as the new candidate; then increment the counter if the element equals the candidate, otherwise decrement it. If a majority exists, it is the final candidate. O(n) time, O(1) space. If a majority is not guaranteed, verify with a second pass.

#include <stdbool.h>
#include <stddef.h>

bool majority(const int *a, size_t n, int *out)
{
    int cand = 0;
    size_t count = 0;
    for (size_t i = 0; i < n; i++) {
        if (count == 0) cand = a[i];
        count += (a[i] == cand) ? 1 : (size_t)-1;   /* +1 or -1 */
    }
    size_t c = 0;                                    /* verification pass */
    for (size_t i = 0; i < n; i++) c += (a[i] == cand);
    if (c > n / 2) { *out = cand; return true; }
    return false;
}
/* {2, 2, 1, 1, 1, 2, 2} -> 2 */

Why it works: each decrement pairs one occurrence of the candidate with one different element and "cancels" both. A majority element has more occurrences than all other elements combined, so it cannot be fully cancelled and survives as the candidate.

Dry run {2, 2, 1, 1, 1, 2, 2}: cand 2 (1), 2 (2), 1 → 1, 1 → 0, 1 becomes cand (1), 2 → 0, 2 becomes cand (1). Final candidate 2; verification count 4 > 3.

Alternatives: sort and take the middle element (O(n log n)); hash counts (O(n) memory); bit-by-bit majority (for each of 32 bit positions, count ones; the majority element has the majority bit in every position).

Embedded use: majority voting of redundant sensor readings or triple modular redundancy (TMR) uses the same idea for 3 values: (a & b) | (a & c) | (b & c) gives the bitwise majority of three words, which corrects a single corrupted copy.

Follow-up: elements appearing more than n/3 times (at most two): Boyer–Moore with two candidates and two counters.