Smallest number with N digits and digit sum S

Easy

Problem

Return the smallest number that has exactly n digits (no leading zero) whose digits add up to s, or −1 if none exists.

Example 1

Input:  n = 2, s = 9
Output: 18

Example 2

Input:  n = 3, s = 20
Output: 299

Also asked as: Find smallest number with given number of digits and sum of digits

Test cases

Case 1

Input:    2, 9
Expected: "18"

Case 2

Input:    3, 20
Expected: "299"

Case 3

Input:    1, 9
Expected: "9"

Case 4

Input:    2, 19
Expected: "-1"

Case 5

Input:    2, 0
Expected: "-1"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Fill from the least-significant digit with 9s

Time O(n)Space O(n)

Reserve 1 for the leading digit (no leading zero), then put as much as possible (9s) into the rightmost positions; the leftover goes to the front.

function smallestNumber(digits, sum) {
if (sum === 0) return digits === 1 ? '0' : '-1';
if (sum > 9 * digits) return '-1';
const res = new Array(digits).fill(0);
sum -= 1; // reserve for the leading digit
for (let i = digits - 1; i > 0; i--) {
if (sum > 9) { res[i] = 9; sum -= 9; } else { res[i] = sum; sum = 0; }
}
res[0] = sum + 1;
return res.join('');
}