Isn't there any more efficient solution for the CodeForces 919-B/Perfect Number question?

Question

So, here's the question:

We consider a positive integer perfect, if and only if the sum of its digits is exactly 10. Given a positive integer k, your task is to find the k-th smallest perfect positive integer.

Input: A single line with a positive integer k (1≤k≤10000).

Output: A single number, denoting the k-th smallest perfect integer.

The solution I've got for this question is:

int main(){
    int k=0, m=19, c=0, sum=0;
    scanf("%d", &k);
    while(true){
        int n = m;
        sum = 0;
        while(n){
            sum+=n%10;
            n=n/10;
        }
        // printf("%d %d %d\n", n, sum, c);
        if(sum == 10) c++;
        if(c == k) break;
        m++;
    }
    printf("%d", m);
    return 0;
}

So, isn't there any solution that is more efficient than this one ?

I've thought about this problem for about an hour and then decided to google the answer. This solution truly disappointed me. I've expected that there will be some tricky math hidden in this problem.

Answer 1

Your intuition is correct, that solution is a naive bruteforce that works for small cases but grows in O(n²) and so quickly slows down as k grows. There is an O(1) (constant time) solution to this:
The question has come up before on math stackexchange and received a beautiful answer outlining the optimal solution here.

Edit:
I missed the part about the digit sum being exactly 10, not divisible by 10...
In this case I'm not sure if there is an optimization, since you really are fully dependant on all digits in your input. Saša's solution on the math exchange question doesn't apply to your case.
The most I can think of to optimize your case is to break early as soon as your sum exceeds 10, and to split large numbers up into smaller parts and compute their sums in parallel, since they are all independant of each other.