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/2times 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.
Core idea: a move that raises n − 1 elements by 1 leaves the gaps between elements unchanged everywhere except at the one element you skipped — so it's the same relative effect as lowering that one element by 1. Stop thinking "raise everyone up to the max" and start thinking "lower everyone down to the min." The answer is then just how far each element has to fall:
sum(nums) − n · min(nums).
Problem, rephrased
You're given a non-empty integer array nums of size n. One move picks any n − 1 of the elements and adds 1 to each of them (you skip exactly one element per move). Return the minimum number of moves to make every element equal.
Picture n water glasses at different levels. Each move tops up every glass but one by a fixed amount. That sounds like you're chasing a moving target — every time you pour, the gaps shift. The trick is to notice you're only ever asked about the relative heights: making them equal is about closing gaps, and "everyone but one goes up by 1" closes the same gaps as "that one goes down by 1." So the cheapest path is to imagine draining each glass down to the level of the shortest one, and count the total amount drained.
nums |
n |
min | Moves |
|---|---|---|---|
[1, 2, 3] |
3 | 1 | (1−1)+(2−1)+(3−1) = 3 |
[1, 1, 1] |
3 | 1 | 0 (already equal) |
[5] |
1 | 5 | 0 (one element is trivially equal to itself) |
[1, 10] |
2 | 1 | 9 |
[0, 0, 5] |
3 | 0 | 5 |
Notice row 1: the official move set ("increment two of the three") gets you there in 3 moves, and sum − n·min = 6 − 3·1 = 3 agrees — the formula counts the same 3 moves without ever simulating them.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson