Find second smallest number from sum of digits and number of digits

Given the sum of digits as S and the number of digits as D, the task is to find the second smallest number

Examples:

Input: S = 9, D = 2
Output: 27
Explanation: 18 is the smallest number possible with sum = 9 and total digits = 2, Whereas the second smallest is 27.

Input: S = 16, D = 3
Output: 178
Explanation: 169 is the smallest number possible with sum is 16 and total digits = 3, Whereas the second smallest is 178.

Approach: To solve the problem follow the below idea:

The idea is to use greedy approach and find the minimum element by filling all digits from least significant digit to most significant one by one, once we found the minimum element then we can easily find the second minimum element by using the next greater element in such a way that the sum of digits should be the same.

Illustration:

Let’s take an example to understand how we can find the second minimum element by using the next permutation concept:

Let minimum number = 10799. 

• Start scanning the given number from the least significant(rightmost) digit to the most significant(leftmost) digit and whenever we found a digit less than 9 then increase it by one and decrease the next digit by one now this number is the second minimum number. 
• Hence 2nd minimum element which is the next permutation of the minimum element = 10889.

Below are the steps for the above approach:

• First, check the base case,
  • If the sum is greater than 9*number of digits that is the maximum possible sum we can get by using D number of digits, then return -1.
  • Check if sum == 1. then it is not possible to get the 2nd minimum element whose sum is greater than 1, hence return -1.
  • Check if D == 1, then only one possible way to get any number with any given sum hence return -1.
• Initialize an empty string ans to store the resulting number and decrease the sum by one because we need to leave 1 for the last digit.
• Now put the maximum possible number of 9 at end of the answer on the least significant side so that we can get the minimum number.
  • Run a loop from D – 1 to 0,
    • Check if the sum is greater than 9, add 9 to the ans, and subtract 9 from the sum.
    • Else add the sum to ans and set sum = 0.
• Add 1 to the sum and append it to the string.
• Reverse the ans string to get the correct ordering of digits.
• Now we have a minimum number we get by using sum and D.
• Now run a loop from the end of the answer to find the rightmost index equal to 9, and store the index in ind variable.
• Decrement the digit at index ind by one, and increment the digit at index ind – 1 by one to get 2nd minimum element.
• Return answer.

Below is the code for the above approach:

Time Complexity: O(D), As we a loop D times.
Auxiliary Space: O(D), As we take a string of size D to store the answer.