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

How to find the smallest number with given digit sum s and number of digits d? Examples :

Input  : s = 9, d = 2
Output : 18
There are many other possible numbers 
like 45, 54, 90, etc with sum of digits
as 9 and number of digits as 2. The 
smallest of them is 18.

Input  : s = 20, d = 3
Output : 299
class Solution {
    public int[] findSmallest(int n, int sum) {
        if (sum == 0) {
            if (n == 1)
                return new int[] { 0 };
            return new int[0];
        }
        if (sum > 9 * n)
            return new int[0];
        int[] res = new int[n];
        // There must be 1 left for the most significant digit
        sum -= 1;

        for (int i = n - 1; i > 0; i--) {
            if (sum > 9) {
                res[i] = 9;
                sum -= 9;
            } else {
                res[i] = sum;
                sum = 0;
            }
        }
        res[0] = sum + 1; // The initially subtracted 1 is incorporated here
        return res;
    }
}

Last updated