Find smallest number with given number of digits and sum of digits

The problem, simply

You get two numbers: d, how many digits the answer must have, and s, what its digits must add up to. The answer cannot start with 0 (unless it is the single digit 0).

Give back the smallest such number as a string, or "-1" if no such number exists.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count up from the smallest d digit number, 10^(d-1), and stop at the first one whose digits add up to s.

1. If s is more than 9 * d, return -1.
2. For every number from 10^(d-1) to 10^d - 1, add up its digits.
3. Return the first number whose digit total is s.

class Solution {
    public String smallestNumber(int d, int s) {
        if (s > 9 * d || d > 18) return "-1";      // too big for a long anyway
        if (s == 0) return d == 1 ? "0" : "-1";
        long from = 1;
        for (int i = 1; i < d; i++) from *= 10;    // smallest number with d digits
        for (long x = from; x < from * 10; x++) {
            if (digitSum(x) == s) return Long.toString(x);
        }
        return "-1";
    }

    private int digitSum(long x) {
        int sum = 0;
        while (x > 0) { sum += x % 10; x /= 10; }
        return sum;
    }
}

How long it takes: up to 9 * 10^(d-1) numbers, each summed in O(d), so O(10^d * d). Extra room: O(d) for the string. Fine for 6 digits, useless for 100.

Way 2: the clever way

Fill the digits from the right, the way the marbles go into cups.

1. If s > 9 * d, or s == 0 with more than one digit, return -1.
2. Save one unit for the first digit: left = s - 1.
3. Walk from the last place to the second place. Put min(9, left) there and take it away from left.
4. The first place gets left + 1.

Why is this the smallest? Comparing two numbers of the same length, the first place where they differ decides. Putting as much as possible at the back leaves the least for the front places, so every front place is as small as it can be.

class Solution {
    public String smallestNumber(int d, int s) {
        if (s > 9 * d) return "-1";                  // cannot reach the total
        if (s == 0) return d == 1 ? "0" : "-1";      // only the number 0 has total 0

        char[] digits = new char[d];
        int left = s - 1;                            // keep 1 for the front digit
        for (int i = d - 1; i >= 1; i--) {
            int put = Math.min(9, left);             // stuff the back with 9s
            digits[i] = (char) ('0' + put);
            left -= put;
        }
        digits[0] = (char) ('0' + left + 1);         // the front gets the rest
        return new String(digits);
    }
}

How long it takes: one step per digit, O(d). Extra room: the answer, O(d).

Watch out for

• s = 0 is only possible when d = 1.
• s > 9 * d is impossible. Check it first.
• d can be up to 100 or more, so build a string. A long holds at most 18 digits.

What interviewers ask next

• The largest number instead? Fill from the left with 9s: each place gets min(9, left). No saved 1 is needed because a big front digit is welcome.
• How many d digit numbers have digit total s? Dynamic programming over places and totals, O(d * s * 10).
• Smallest number whose digits multiply to a given value? Break the value into factors 9, 8, ..., 2 greedily from 9 down, then sort the digits.
• Next bigger number with the same digit total? Find the rightmost place you can raise by 1 while taking 1 from a place after it, then make the tail as small as possible.

Remember this

Grown-up words: the cups are digit positions, the marbles are the digit sum, and building the answer one place at a time with the best local choice is a greedy construction.