Smallest number

Given two integers s and d. The task is to find the smallest number such that the sum of its digits is s and the number of digits in the number are d. Return a string that is the smallest possible number. If it is not possible then return -1.

Examples:

Input: s = 9, d = 2
Output: 18 
Explanation: 18 is the smallest number possible with the sum of digits = 9 and total digits = 2.

Input: s = 20, d = 3 
Output: 299 
Explanation: 299 is the smallest number possible with the sum of digits = 20 and total digits = 3.

Expected Time Complexity: O(d)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ s ≤ 100
1 ≤ d ≤ 6

Approach 01:

#include <cmath>
#include <string>

class Solution {
    // Function to check if a number has a given sum of digits and a specific number of digits
    bool hasSumAndDigitCount(int number, int requiredSum, int requiredDigits) {
        int digitSum = 0, digitCount = 0;
        while (number) {
            digitSum += (number % 10);
            digitCount++;
            number /= 10;
        }
        return digitSum == requiredSum && digitCount == requiredDigits;
    }

public:
    std::string smallestNumber(int requiredSum, int digitCount) {
        // If the required sum is greater than the maximum possible sum for the given digit count
        if (requiredSum > 9 * digitCount) return "-1";

        // Loop through all numbers with the given digit count
        for (int number = pow(10, digitCount - 1); number < pow(10, digitCount); number++) {
            // Check if the current number has the required sum of digits and the required digit count
            if (hasSumAndDigitCount(number, requiredSum, digitCount)) {
                return std::to_string(number);
            }
        }
        return "-1"; // Return -1 if no such number is found
    }
};

class Solution:
    # Function to check if a number has a given sum of digits and a specific number of digits
    def has_sum_and_digit_count(self, number: int, required_sum: int, required_digits: int) -> bool:
        digit_sum = 0
        digit_count = 0
        while number:
            digit_sum += (number % 10)
            digit_count += 1
            number //= 10
        return digit_sum == required_sum and digit_count == required_digits

    def smallestNumber(self, required_sum: int, digit_count: int) -> str:
        # If the required sum is greater than the maximum possible sum for the given digit count
        if required_sum > 9 * digit_count:
            return "-1"

        # Loop through all numbers with the given digit count
        for number in range(10**(digit_count - 1), 10**digit_count):
            # Check if the current number has the required sum of digits and the required digit count
            if self.has_sum_and_digit_count(number, required_sum, digit_count):
                return str(number)

        return "-1"  # Return -1 if no such number is found

Time Complexity

• Initialization and Input Handling:

  Checking if the requiredSum is greater than 9 * digitCount takes \( O(1) \) time.

• Looping through Numbers:

  Looping from pow(10, digitCount - 1) to pow(10, digitCount) involves iterating through \( 9 \times 10^{(\text{digitCount} – 1)} \) numbers. In the worst case, this results in \( O(10^{\text{digitCount}}) \) time complexity.

• Digit Sum and Count Check:

  For each number, checking the sum of digits and digit count takes \( O(\text{digitCount}) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(\text{digitCount} \times 10^{\text{digitCount}}) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for variables like digitSum, digitCount, and the resulting number, leading to \( O(1) \) auxiliary space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).