A counter changes only in steps of two, so its residue modulo 2 never changes: what does an odd reading prove?
answer
- look for what never changes
- each step moves by a multiple
- the residue is fixed for all time
- an odd value falsifies a premise
- necessary for reachability, not sufficient
basics
~20 sAn odd reading proves the counter was not produced by those steps alone: either it started odd, or a write outside the listed operations touched it. A preserved residue converts an impossible value into a search filter.
solid answer
~50 sIf every operation changes a quantity by a multiple of `k`, then the quantity's residue modulo `k` is the same after every operation as it was at the start - because addition is well defined on residue classes and adding a multiple of `k` is adding the zero class. With `k = 2` and steps of `+2` or `-2`, an even start stays even forever. So an odd reading does not mean a rare interleaving or a large number of steps; it means one of the two premises is false. Either the initial value was odd, or something wrote to the counter that is not in the list of operations you enumerated. That narrows the investigation before any log is opened, and it rules out an infinite set of histories rather than the ones you happened to test.
code
pseudocode · 11 linescount = 0 // start in the even class
for each event in stream:
if event is PAIR_ADDED:
count = count + 2
else if event is PAIR_REMOVED:
count = count - 2
else:
ignore event
assert (count mod 2) == 0 // holds after every branch abovego deeper
Remember the shape of the claim: if every step changes a number by two, the number stays even, so an odd value cannot have come from those steps.
Explain why the residue is preserved - adding a multiple of the modulus adds the zero class - and state what an odd value therefore falsifies about the model.
Use it as a triage tool: an impossible residue points at the initial value or at an unlisted writer, which narrows the search before any reproduction attempt.
Decide where invariants are worth engineering in - choosing operations so that a cheap residue check covers a whole class of corruption is a design lever, not a debugging trick.
## What a modular invariant is An **invariant modulo k** is a quantity whose residue class modulo `k` is the same after every permitted operation as before it. The check is local and cheap: look at each operation in isolation and ask by how much it changes the quantity. If every change is a multiple of `k`, the residue never moves, because adding a multiple of `k` adds the zero class and addition is well defined on classes. The payoff is global and disproportionate. A local check over a handful of operations yields a statement about **every** reachable state, no matter how long or strangely interleaved the history was. No amount of testing produces a statement of that shape. ## The argument in the direction it is valid 1. Establish the residue of the initial state. With a counter starting at zero, that is the class `0` modulo `2`. 2. Check every operation. `+2` and `-2` both change the value by a multiple of `2`, so both leave the class alone. 3. Conclude: every reachable state has residue `0` modulo `2`. Therefore any state with residue `1` is **unreachable**. The direction matters and gets inverted constantly. The invariant is a **necessary** condition for reachability, not a sufficient one. It proves odd values impossible; it proves nothing about which even values can actually occur, since bounds, ordering constraints and other invariants may still block them. "Same residue" is not a certificate of reachability. ## Reading an odd value as a diagnosis An observed odd value falsifies the conjunction of the two premises, so exactly one of these must be true: - The **initial value** was not what you assumed - a seeded field, a restored snapshot, a default that was never zero. - The **operation list is incomplete** - a second writer nobody enumerated, a repair path, an administrative adjustment, a single-step increment that exists somewhere in the code but not in the documented set. - The **observation is not of that quantity** - a report that sums two different counters, or a value assembled from parts taken at different moments. Every one of those is a concrete place to look, and the invariant found them without reproducing anything. The weak move is to treat the odd number as a display glitch or a transient to be re-checked later; an invariant argument says the value cannot exist under the stated model, and the model is what is wrong. ## Generalising past parity Parity is only the smallest case. If the permitted operations change the quantity by amounts drawn from a set `S`, the achievable total changes are exactly the integer combinations of `S`, which are the multiples of `gcd(S)`. | permitted changes | invariant modulus | what is excluded | |---|---|---| | +2, -2 | 2 | every odd value | | +3, -3, +6 | 3 | every value not congruent to the start modulo 3 | | +3, -5 | 1 | nothing - gcd is 1, so no modulus is preserved | That last row is the honest limit: a pair of step sizes sharing no factor preserves no residue at all, and looking for an invariant there is wasted effort. Before reaching for the argument, compute the greatest common divisor of the step sizes; it tells you immediately whether there is anything to find. The same reasoning covers quantities that are not literally counters. A weighted total where every move adds and removes the same weight, a balance where each transaction posts two equal entries, a queue depth changed only in pairs - each is a modular invariant in disguise, and each turns a class of corrupt states into states you can declare impossible rather than merely improbable.
- Does a state whose residue matches the invariant have to be reachable?No. The invariant is necessary, not sufficient: it excludes every state with the wrong residue and says nothing about the rest. Other constraints - bounds, ordering, a second invariant - can still make a residue-compatible state impossible, so matching residues is never a proof of reachability.
- How does the argument change when operations add 3 and subtract 5?It disappears. The reachable changes are the integer combinations of the step sizes, which are the multiples of their greatest common divisor, and `gcd(3, 5) = 1`. Every residue is then reachable, so no modulus is preserved and there is no invariant of this kind to find.
- Why is this stronger than adding a test that the counter stays even?A test observes the executions it runs. The invariant argument covers every execution, including interleavings and lengths nobody will ever run, because it only inspects each operation's effect in isolation. A passing test suite is consistent with the property being false on a path not taken.
A double-entry ledger where every transaction posts an equal debit and credit keeps its net at the same value forever, so a non-zero net is not a small error to chase down - it proves an entry was made outside the posting rules.
saying these in an interview costs you the question
- Dismissing the odd reading as a display or rounding artefact
- Assuming a matching residue proves a state is reachable
- Thinking enough passing runs establish the invariant the argument already gives
- Searching for a rare interleaving that the operations cannot produce at all
- Expecting an invariant to exist when the step sizes share no common factor