algorithm - 找到数字和等于某个数的最小正整数

Question

给定一个数字，假设 t = 10。我们的任务是找到最小的正整数，使得它的数字之和等于 10。在这个例子中，最小的整数是 19 (1+9=10)。

我想出了以下解决方案:

我想我们肯定可以使用搜索来解决这个问题。对于上面的例子，t = 10 表示一位数(1-9)不能计算，我们就从第一个两位数的正整数10开始，然后逐步搜索，直到找到正确答案19 .

起始搜索点有一个通用公式。

• 对于一位数，最大数字和为:9
• 对于两位数，最大位数和为:18
• ...

所以给定 t = 10，我们可以用 t/9 + 1 知道起始搜索数应该是一个两位数。最小两位数为 10。

我的问题是线性搜索有点耗时。还有没有解决这个问题的有效方法？或者甚至有任何通用公式这个问题？

更新

尽可能使用9，然后将余数放在最前面。

感谢 Teepeemm 和 John Coleman。

例如:t = 25, 25 = 9+9+7。把7放在两个9前面生成整数 799。

Answer 1

解决办法是尽可能多的使用9，然后把余数放在最前面。这使得余数(答案的前导数字)尽可能小，并使用尽可能少的数字。伪代码:
string( input % 9 ) + stringMult( '9', input/9 );