Smallest Impossible Sum — Solution & Editorial

Back to the Problem

Sort. If every value up to R is reachable and the next coin c ≤ R+1, reachability extends to R+c; the first coin with c > R+1 freezes the answer at R+1.

Complexity: O(N log N)

Watch out: The running reach exceeds 32 bits with 10⁵ coins of 10⁹.