Last Updated: 11 Feb, 2021
Smallest Number
Easy
Asked in companies
You are given two positive integers ‘N’ and ‘K’. Your task is to find the smallest ‘N’ digit number whose sum of digits equals ‘K’. If no such number exists then you need to print -1.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘K’.
Output Format :
For each test case, print the smallest ‘N’ digit number as a string whose sum of digits equals ‘K’. If no such number exists then you need to print “-1”, without quotes.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 5000
0 <= K <= 10^6
Where ‘T’ is the number of test cases, ‘N’ is the total number of digits and ‘K’ denotes sum of digits that the required number should have.
Time Limit : 1sec
Approaches
The idea here is to fill the digits greedily. The first digit should be 1 then we will try to maximize the digits having zero. So, we will fill all back digits of the number using digit 9 and first digit with 1. Also, we will fill the remaining digits with 0.
Algorithm:
- If ‘K’ = 0 then if ‘N’ = 1 then return “0” else return “-1” as there does not exist a number whose sum of digits equals 0 and the number of digits greater than 1.
- If K > 9 * N, then return -1 as a number having ‘N’ can have a maximum 9 * N sum by filling all digits with 9.
- Declare an empty string to store the smallest number, say ‘answer’.
- Subtract 1 from ‘K’.
- Run a loop from i =‘N’ – ‘1’ to 1.
- If K > 9 then add digit 9 to the ‘answer’
- Else add digit ‘K’ to the answer and set ‘K’ as zero.
- Add digit ‘K’ + 1 to the answer.
- Reverse the ‘answer’ string.
- Finally, return the ‘answer’.