147. Smallest Number With Given Number of Digits and Digit Sum

Given the number of digits d and a target digit sum s, find the smallest d-digit number (no leading zero, unless d = 1 and s = 0) whose digits add up to exactly s. If no such number exists, print -1.

Input: The first line contains an integer d, the number of digits. The second line contains an integer s, the target digit sum. Output: Print the smallest d-digit number whose digits sum to s, or -1 if no such number exists.

1 <= d <= 10^5, 0 <= s <= 9*d

The single-digit exception (d=1, s=0 allows the answer '0') is a special edge case explicitly carved out from the general 'no leading zero' rule - easy to overlook if focused only on the general multi-digit construction logic.

Find the smallest d-digit number (no leading zero) whose digits add up to exactly a target sum. Brute force: Try every possible d-digit number in ascending order and check if its digits sum to the target - this could take an enormous number of checks for larger d, when a direct greedy construction builds the answer immediately. Optimised: Since smaller leftmost digits always produce a smaller overall number (for a fixed digit COUNT), and pushing the maximum possible digit sum toward the rightmost positions leaves the leftmost positions as small as they can be, this direct greedy construction (fill from the right, cap at 9) builds the true smallest valid number without ever needing to check or generate alternative candidates.

Recursively try every digit (0-9, or 1-9 for the leading position) at each of the d positions left to right, and whenever a complete d-digit number is formed, check whether its digits sum to exactly s; among all that qualify, keep the smallest. This tries every possibility so it cannot miss a valid answer, but the number of full digit assignments to explore grows exponentially with d, making it impossible to run for d up to 10^5. Time: O(10^d) Space: O(d)

First check feasibility directly: if s is 0 and d > 1, or if s exceeds 9*d, no valid number exists. Otherwise, to keep the number as small as possible, the digit sum should be pushed as far right (least significant) as possible, since large digits hurt the number less the further right they sit. Fill positions from the last digit backwards, assigning each one min(remaining sum, 9) and subtracting that from the remaining sum, until the remaining sum is used up (the untouched leading positions default to 0, except the first digit gets bumped to at least 1 when needed). This produces the same minimal answer as the left-to-right greedy but with a simpler single pass that only ever needs to compare the remaining sum against 9, with no bound arithmetic per digit. Time: O(d) Space: O(d)

Build the number digit by digit from the leftmost (most significant) position, and at each position choose the smallest digit x (starting from 1 for the very first digit, or 0 for others) such that the remaining positions can still absorb the leftover sum - that is, 0 <= (s so far remaining - x) <= 9 * (positions left after this one). Because a smaller digit in a more significant position always yields a smaller number, greedily picking the smallest feasible digit at each step and only checking a simple bound (rather than truly backtracking) produces the correct minimal number in a single left-to-right pass. Time: O(d) Space: O(d)

1. To keep the number small, keep the LEFTMOST digits as small as possible - meaning push as much of the digit sum as possible into the RIGHTMOST digits (maxing each at 9). 2. The leading digit must be at least 1 (except the special single-digit, sum-0 case where 0 is allowed) - reserve that minimum 1 first. 3. Greedily fill from the rightmost position backward with the remaining sum, placing as much as possible (up to 9) at each position.

Time: O(d) - one pass to reserve the minimum leading digit, one pass filling from the right. Space: O(d), for the resulting digit string.

s = 0 with d = 1 (the only case a leading zero is allowed), s outside the achievable range (e.g. s = 0 with d > 1, or s > 9*d, printing -1), and d at its maximum of 10^5 to confirm the greedy digit fill runs efficiently.

Be ready to state the two infeasibility conditions clearly: if the target sum exceeds 9*d (even maxing every digit at 9 isn't enough), or if s is 0 but d>1 (a leading zero would be required for a multi-digit number) - either case means printing -1.