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

Problem Statement

Given the number of digits d and the sum of digits s, find the smallest number having d digits with digit sum equal to s.

Constraints:

• 1 ≤ d ≤ 100
• 1 ≤ s ≤ 900

Example:

• Input: d = 2, s = 9
• Output: 18
• Explanation: 18 is the smallest 2-digit number with digit sum 9 (1+8=9)

Example 2:

• Input: d = 3, s = 20
• Output: 299
• Explanation: 2+9+9 = 20

Example 3:

• Input: d = 2, s = 1
• Output: 10
• Explanation: 1+0 = 1, and 10 is smaller than any other 2-digit number with sum 1

Approach 1: Brute Force (Try All Numbers)

Intuition

Iterate through all d-digit numbers and find the smallest one with digit sum equal to s.

Algorithm

1. Start from the smallest d-digit number (10^(d-1))
2. For each number, calculate digit sum
3. Return first number with sum = s
4. If no such number exists, return -1

public class Solution {
    private int digitSum(long n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
    
    public String smallestNumber(int d, int s) {
        if (s > 9 * d || s < 1) return "-1";
        
        long start = 1;
        for (int i = 1; i < d; i++) start *= 10;
        
        long end = start * 10 - 1;
        
        for (long num = start; num <= end; num++) {
            if (digitSum(num) == s) {
                return String.valueOf(num);
            }
        }
        
        return "-1";
    }
}

Complexity Analysis

• Time Complexity: O(10^d) - In worst case, iterate through all d-digit numbers
• Space Complexity: O(d) - For storing the result string

Approach 2: Greedy Construction (Optimal)

Intuition

To get the smallest number:

1. First digit: Use the smallest possible digit (at least 1 to avoid leading zeros)
2. Remaining digits: Fill from right with largest possible digits (9s)

Strategy:

• Start from the rightmost position
• Place 9 if remaining sum allows, otherwise place remaining sum
• For the first digit, ensure at least 1

Algorithm

1. Check if valid solution exists (s between 1 and 9*d)
2. Build number from right to left
3. For each position (except first), place min(9, remaining_sum)
4. For first position, place remaining sum (at least 1)

public class Solution {
    public String smallestNumber(int d, int s) {
        // Check if solution exists
        if (s > 9 * d || s < 1) return "-1";
        
        char[] result = new char[d];
        int remaining = s;
        
        // Fill from right to left
        for (int i = d - 1; i >= 0; i--) {
            if (i == 0) {
                result[i] = (char)('0' + remaining);
            } else {
                int digit = Math.min(9, remaining - 1);
                result[i] = (char)('0' + digit);
                remaining -= digit;
            }
        }
        
        return new String(result);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.smallestNumber(2, 9));   // Output: 18
        System.out.println(sol.smallestNumber(3, 20));  // Output: 299
        System.out.println(sol.smallestNumber(2, 1));   // Output: 10
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(d) - Single pass through d digits
• Space Complexity: O(d) - For storing result

Finding the Largest Number

A related problem: find the largest d-digit number with digit sum s.

Variant: Count Numbers with Given Digit Sum

Key Takeaways

1. Greedy Construction: Build number from right to left
2. First Digit Constraint: Must be at least 1 (no leading zeros)
3. Fill with 9s: Place largest digits (9s) in rightmost positions
4. Validity Check: Sum must be between 1 and 9×d
5. Time Efficiency: O(d) instead of exponential brute force
6. Related Problems: Largest number with digit sum, count of numbers
7. Edge Cases: d=1 with s=0 (invalid), s > 9×d (impossible)