Rajat lost the password of his super locker. He remembers the number of digits N as well as the sum S of all the digits of his password. He know that his password is the largest number of N digits that can be made with given sum S. As he is busy doing his homework, help him retrieving his password.

Example 1:

```Input:
n = 5, s = 12
Output:
93000
Explanation:
Sum of elements is 12. Largest possible
5 digit number is 93000 with sum 12.
```

Example 2:

```Input:
n = 3, s = 29
Output:
-1
Explanation:
There is no such three digit number
whose sum is 29.```

Algorithm: Greedy approach

• Check whether given sum is greater than 9*n.
• If it is greater return -1 because maximum achievable sum is 9*n.
• Run a loop n times.
• In each iteration check if sum is greater than 9. Add 9 to final string if sum is greater or add sum.
• Update the sum
• Return the final string.

c++ implementation:

```    string largestNumber(int n, int s)
{
string r="";

if(n*9<s)
{
r=r+"-1";
}
else
{
while(n && s)
{
if(s<9)
{
r=r+to_string(s);
s=0;
}
else
{
r=r+"9";
s=s-9;
}

n=n-1;
}
while(n)
{
r=r+"0";
n=n-1;
}
}

return r;
}```

Time Complexity : O(n)
Space Complexity: O(n)

darkmode