Question: Given a certain number, saying t = 10. Our task is to find the minimum positive integer such that the sum of its digits equals 10. In this example, the minimum integer is 19 (1+9=10). 

I came up with the following solution:

I guess we definitely can use search to solve this problem. For the above example, t = 10 means that one-digit number (1-9) cannot work, we just start from the first 2-digit positive integer which is 10 and then search step by step until finding the correct answer which is 19.

There is a general formula for the start search point.

* For one-digit numbers, the maximum sum of digits is: 9
* For two-digit numbers, the maximum sum of digits is: 18
* ...

So given t = 10, we can use t/9 + 1 to know that the start search number should be a two-digit number. The minimum two-digit number is 10.

My Question is that linear search is kind of time-consuming. Is there any more
efficient way to solve this problem? Or is there even any general formula for 
this problem?

Update
------

Using 9 as much as possible and then put the remainder at the front.

Thanks Teepeemm and John Coleman. 

For example: t = 25, 25 = 9+9+7. Put 7 in front of two 9s to generate
the integer 799.

Answer: 
The solution is to use as many 9’s as possible, and then put the remainder at the front. This makes the remainder (leading digit of the answer) as small as possible, and uses as few digits as possible. In pseudo code:  

`string( input % 9 ) + stringMult( '9', input/9 );`
I have found a general formula to find the smallest number whose digits sum up to **S** and has **M** digits. Here is a python implementation of it:

```
def bla(M,S):
    n=(S+7)//9
    sl=9*n -7
    c=10**(n-1)
    b=10**(M-1)
    p=int((2+S-sl)*c -1)
    return p+b

```

If you have any doubts please comment below.