Find the Kth smallest number whose digits have a sum of 10

The main issue of your code is that you limit the search for values less than 20000.

In order to improve the efficiency, I added two tricks

• I avoid to perform the same calculation several times, by memorizing the previous results
• According to the value of the sum of the digits, I adjust the value of the increment

On my PC, it takes 0.15s to calculate the maximum value (for k = 20000).

Additional explanations

In the code, the i variable corresponds to the candidates, i.e. the values that we test whether the sum of digits is equal to 10 or not.

num corresponds the the index of found solutions. A solution corresponds to a number, the sum of digits of which is equal to 10. mem[num] = i means that i is the num^th solution. k has the same meaning as in OP's code: we want to find the k^th number such that sum of digits = 10.

The two lines int kmax = 1; mem[1] = 19; use the fact that 19 is the first valid solution. This is needed to initialise the management of the mem vector, which memorizes all found solutions.

The tricks used to accelerate the process are the following:

• if the sum of current number i is equal to 10, then we know that there is no other solution between i and i+8. For example, after 27, the next solution is equal to 36. So we can do i += 9 instead of simply i++.
• if the sum is higher than 10, then we will not find solution by simply increasing the first digit. For example, if i = 85, we can go directly to 90, i.e. nulling the least digit. This is performed with i += (10 - i%10);
• if the sum is less than 10, e.g. 5, then you can directly add 5 instead of 1. This is performed with i += (10 - total);

In practice, it could be possible to go further. For example, if i = 99000, then we could directly add 1000 instead of 10. I did not go so far, as the obtained code seems over-skill already a little bit (0.15s instead of 1s).

#include <iostream>
#include <vector>

int sum(int d) {
    int ans = 0;
    while(d) {
        ans += d%10;
        d /= 10;
    }
    return ans;
}

int main() {
    int t;
    std::cin >> t;
    std::vector<int> mem(20001, 0);
    int kmax = 1;
    mem[1] = 19;
    while(t-- >0) {
        int i, k;
        std::cin >> k;
        int num = 1;
        if (k > kmax) {
            i = mem[kmax];
            num = kmax;
            while(true) {
                int total = sum(i);
                if(total == 10) {
                    mem[num] = i;
                    if (num == k) break;
                    num++;
                    i += 9;
                } else {
                    if (total > 10) {
                        i += (10 - i%10);
                    } else {
                        i += (10 - total);
                    }
                }
            }
            kmax = k;
        }
        std::cout << mem[k] <<"\n";
    }
    return 0;
}

Here's the obligatory digit dynamic-program for completeness. This one will let you find the 200,000th (never mind 20,000th) almost immediately with binary search.

JavaScript code:

function g(digits, i, sum, bound, memo){
  const key = String([i, sum, bound]);

  if (memo.hasOwnProperty(key))
    return memo[key];
    
  if (sum == 0)
    return memo[key] = 1;
    
  if (i == 0)
    return sum <= (bound ? digits[0] : 9);

  let result = 0;
  
  const k = bound ? digits[i] : 9;

  for (let d=0; d<=k && d<=sum; d++){
    const _bound = digits[i] == d ? bound : 0;
    result += g(digits, i-1, sum-d, _bound, memo);
  }
  
  return result;
}


function f(n, sum){
  const digits = [];
  
  while(n){
    digits.push(n % 10);
    n = Math.floor(n/10);
  }
  
  return g(digits, digits.length-1, sum, 1, {});
}

console.log(f(320002210, 10));

console.log(f(320002209, 10));

You can solve this problem in a "recursive" way.

If a given number starts with the digit d, then the digits that follow must have the sum 10-d. As the numbers do not exceed 20000, they have at most 5 digits and the first is one of 0, 1.

A simple solution is to use four nested loops. Then you check if the last digit is legal.

n= 0
for d4= 0 to 1
    for d3= 0 to min(9, d-d4)
        for d2= 0 to min(9, d-d4-d3)
            for d1= 0 to min(9, d-d4-d3-d2)
                d0= 0 d-d4-d3-d2-d1
                if 0 <= d0 and d0 <= 9:
                    n+= 1
                    if n == k stop

Some micro-optimizations are possible. Using this method, I find 502 distinct solutions.

I had made a misinterpretation of the constraints but finally here is the solution. the 1<=K<=2*10^4 constraint was for the variable K, the value of the number X was a positive integer hence I initialised x=1. I applied a break statement(so as to take execution out of it when the number is found and printed) inside the infinite loop i.e while(1).

Topics included are: Recursion, Iterations, if statements, Loop control statements.

#include <bits/stdc++.h>

using namespace std;

int main()

{
  //write your code here

  //ios_base::sync_with_stdio(false);

 // cin.tie(NULL);

  int t;

  cin>>t;

  while(t>0)

  {

    int k;

    cin>>k;

    int x=1;

    while(1)

    {

     int sum=0;

     int d=x;

     while(d!=0)

     {

     sum+=d%10;

      d/=10;

     }

      if(sum==10)

      k--;

      if(k==0)

      {

      cout<<x<<"\n";

      break;

      }

      x++;

    }

    t--;

    }

     return 0;

     }