How do you compute the gcd of a whole array of package sizes, including zero entries?

## The fold, and why 0 is the correct seed A warehouse needs the largest crate unit that divides every package size exactly — the gcd of the whole list. Because `gcd(gcd(x, y), z) = gcd(x, gcd(y, z))` and `gcd(x, y) = gcd(y, x)`, the multi-argument gcd is well defined and independent of order, so a single left fold computes it: ``` g = 0 for i in 0..n-1: g = gcd(g, sizes[i]) if g == 1: break return g ``` Seeding at 0 is the mathematically correct choice, not a convenience. Since every integer divides 0, `gcd(0, x) = x`, which makes 0 the identity element of the gcd operation — exactly what a fold's initial accumulator should be. It also gives a sensible answer for an empty list (0, meaning "unconstrained") without a special branch. Seeding at 1 is the classic bug: `gcd(1, x) = 1` always, so the fold returns 1 no matter what the data says. ## Cost, and why the bound overstates it The crude bound is `O(n log M)` where `M` is the largest size: `n` gcd calls, each logarithmic. The real cost is far lower, for two reasons. - The accumulator is **monotonically non-increasing**. After the first element or two it is typically small, and a gcd call with a small first argument terminates in very few steps. - Divisor chains are short. Each time `g` actually decreases, it drops to a proper divisor of itself, at least halving. So `g` can strictly decrease only about `log M` times across the entire pass — every other element costs one cheap remainder that changes nothing. The **early exit at 1** is the operationally important one. Real package sizes are rarely all multiples of a common unit, so with a million entries the accumulator usually hits 1 within a handful of elements and the loop stops there. Without the break you would pay a million pointless calls to confirm an answer already known to be final; with it, the pass is effectively constant-time on typical data. The property that licenses the break is that the gcd can never increase — 1 divides everything, so no later element can lift the accumulator. ## Zeros, negatives and the empty case A zero-size package is the interesting edge. Mathematically it imposes no constraint, because every integer divides 0, so the fold correctly ignores it. Operationally, a zero-size package is almost certainly bad data, and silently absorbing it is the wrong default: the crate unit computed from a list containing phantom zero-size items is still correct, but the inventory it was computed from is not. The senior answer is that the arithmetic handles zeros gracefully **and** the pipeline should still surface them. If every entry is 0, the fold returns 0, which is the conventional value for `gcd(0, 0)` and reads as "any crate unit works". Callers that then divide by the result must guard against that. Negative values should be normalised to absolute values first, since divisibility ignores sign, and mixing signs into a routine that assumes non-negative inputs is a reliable source of infinite loops or negative answers. ## Scale and parallelism Associativity means the fold is a reduction, so a million sizes can be split across shards, each producing a partial gcd, and the partials combined with the same operation. The result is identical regardless of the split, which is a rare and valuable property in a distributed aggregation: no ordering guarantees are needed, retries are idempotent in effect, and a late-arriving batch can simply be folded into the running value. Streaming works the same way — keep one running accumulator, and the answer after every element is the gcd of everything seen so far. ## A neighbouring use of the same primitive The gcd of a pair also answers a coverage question that shows up in sampling: if a sampler visits every k-th slot in a ring of `n` slots, it touches all `n` slots exactly when `gcd(k, n) = 1`. When the gcd is `d > 1`, the walk is trapped in a cycle of `n/d` slots and never reaches the rest — the same reason a stride chosen carelessly against a power-of-two ring size covers only a fraction of it. Being able to state the coprimality condition, rather than testing strides empirically, is the difference between a sampler you can reason about and one you tune by trial. ## What a strong answer covers The fold itself is one line, so the signal is in everything around it: the identity seed, the early exit and why it is valid, the treatment of zeros as both mathematically harmless and operationally suspicious, the empty and all-zero cases, and the observation that associativity makes the whole thing shardable.