Smallest Number with N Digits and Digit Sum S

Smallest Number with N Digits and Digit Sum S is a clean greedy problem. It teaches a core greedy habit: figure out where a quantity does the least damage, and pour it there first.

The slow way first

You could try every n-digit number in order and return the first whose digits sum to s. For n = 7 that is millions of candidates, and it only gets worse — this brute-force search is hopeless for large n.

The question to ask: to make a number small, where should the big digits go? A digit in a higher place value (further left) costs far more than the same digit on the right. So to keep the number small, we want the left digits tiny and the right digits large.

The idea: pour 9s in from the right

Walk the slots from the rightmost to the leftmost. At each slot, place as much sum as it can hold — min(9, remaining) — and subtract that from remaining. The big chunks land on the right where they cost the least, and whatever is left over trickles into the leading digit.

Two guard rails. If s < 1 there is no valid leading digit (a number cannot start with 0), and if s > 9 * n even all 9s cannot reach the sum — both cases are impossible, so we return "-1" up front. Otherwise the greedy fill always works, and the leading digit ends up at least 1.

Walk through it

Step through the animation. The pointer i starts at the rightmost slot. With s = 20: the first slot takes 9 (remaining 11), the next takes 9 (remaining 2), and the leading slot takes the remaining 2. The digits read 2, 9, 9 → "299".

Pseudocode

if s < 1 or s > 9 * n:
    return "-1"                       # impossible
make a list of n zeros called digits
remaining = s
for i from the last slot down to the first:
    digits[i] = min(9, remaining)     # pour in as much as fits
    remaining = remaining - digits[i]
return digits joined into a string

The Python solution

def smallest_number(n, s):
    if s < 1 or s > 9 * n:
        return "-1"
    digits = [0] * n
    remaining = s
    for i in range(n - 1, -1, -1):
        digits[i] = min(9, remaining)
        remaining -= digits[i]
    return "".join(map(str, digits))

• The first guard returns "-1" when the sum is impossible: too small for a leading digit, or too big even for all 9s.
• digits is the list of slots, left to right; remaining is how much sum is still unplaced.
• The loop runs i from n - 1 down to 0, so we fill the rightmost slots first.
• Line 7 is the greedy move: each slot grabs min(9, remaining) — the most it can legally hold.
• When the loop ends, remaining is 0 and the leading digit holds the leftover, which is at least 1 because s >= 1.

Complexity

We touch each of the n slots exactly once, so the work is linear in the number of digits. The only space is the digits list itself.

When this pattern shows up

Practice