# Largest number with given sum

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)

Space Complexity: O(n)