Smallest Number

Easy
0/40
Average time to solve is 15m
profile
Contributed by
21 upvotes
Asked in companies
OYOGoldman SachsMAQ Software

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 8
3 1
Sample Output 1 :
17 
100
Explanation of Sample Input 1 :
Test Case 1 :  
N = 2 and K = 8. 
All two-digit numbers  whose sum of digits = 8 are [17, 26, 35, 44, 53, 62, 71, 80]
The smallest two-digit number whose sum of digits = 8 is 17. 

Test Case 2 : 
N = 3 and K = 1. 
The smallest three-digit number whose sum of digits = 1 is 100.
Sample Input 2 :
2
4 5 
1 8
Sample Output 2 :
1004
8
Explanation of Sample Input 2 :
Test Case 1 :  
N = 4 and K = 5. 
The smallest four-digit number whose sum of digits = 5 is 1004. 

Test Case 2 : 
N = 1 and K = 8. 
The smallest one-digit number whose sum of digits = 8 is 8.
Hint

Can you solve it greedily?

Approaches (1)
Greedy Approach

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’.
Time Complexity

O(N), where N is the total number digits in the given number.

 

Here, we are running a single loop to calculate the smallest number that takes O(N) time.

Space Complexity

O(N), where N is the total number digits in the given number.

 

We are using a string ‘answer’ that takes O(N) extra space.

Code Solution
(100% EXP penalty)
Smallest Number
Full screen
Console