Minimum Addition to Make Integer Beautiful

Carry toward a cleaner decimal number

If the digit sum of n already does not exceed target, return zero. Otherwise, examine decimal positions from units upward. At a nonzero digit d at place value p, add (10-d) * p; this makes that digit zero and carries into higher positions. Accumulate this addition, update the working number, and recheck its digit sum. The first sequence of such lowest-place round-ups that reaches the target is minimal because changing a higher place first adds at least as much while leaving a lower offending digit intact.

Implementation details

Use a wide integer for both the working value and the accumulated addition: repeated carries can cross a power of ten. It is often simpler to update n += addAtPlace and recompute the digit sum than to hand-simulate every carry incorrectly. At most the number of decimal digits plus one positions are processed, so time is O(d^2) with repeated digit-sum scans, or O(d) with maintained digits, and space is O(1). Test n=19, a number that carries across many nines, an already beautiful value, and target zero if the constraints permit it.