Counting and Voting

What is this?

These tricky problems hinge on one observation: you rarely need to count something directly. Instead, you let opposing elements cancel each other out, eliminate candidates one comparison at a time, or keep a few running tallies and watch the answer emerge from whatever survives. The clever move is realizing that a handful of counters can replace a full bookkeeping pass.

💡 Fun fact: The Boyer-Moore majority vote works because anything occupying more than half the array outlasts every possible cancellation — pair off every other element against it and the majority still has votes left standing.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: When something dominates a collection, you don't have to count it directly — you can let opposing elements cancel out, eliminate candidates pairwise, or track a few running counts and watch the answer emerge from what survives.

The pattern

The cleanest version is voting: keep one candidate and a count. A matching element raises the count, a differing one lowers it, and when it hits zero you adopt the next element. Anything that occupies more than half the array is guaranteed to outlast every cancellation and end as the survivor.

The same cancellation logic powers elimination: ask one comparison per step that lets you discard a candidate permanently, so a linear sweep narrows many possibilities down to one (then verify it).

A softer cousin is the running tally: instead of finding a survivor, you maintain counts of in-progress states and read the answer off the maximum or final tally — no per-element bookkeeping beyond a handful of counters. The shared theme is counts that move against each other so the structure of the answer falls out of the arithmetic.

The problems

• Majority Element — Boyer-Moore voting: hold a candidate and a count, cancel on mismatch; the element appearing more than n/2 times is what remains.
• Find the Celebrity — one elimination pass: each "does A know B" either rules out A or rules out B, leaving a single candidate to confirm.
• Minimum Moves to Equal Array Elements — reframe "raise all but one" as "lower one," so the answer is the sum of differences from the minimum.
• Minimum Number of Frogs Croaking — keep running counts of frogs at each c-r-o-a-k stage; the peak number simultaneously mid-croak is the minimum frogs needed.

Key takeaways

• Cancellation reveals dominance — a majority survives every pairing.
• One smart comparison eliminates — discard a candidate per step, then verify.
• Reframe the operation — "increment all but one" equals "decrement one."
• Running counts beat full counts — track stages, read the peak.