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)