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

Question

Looking for alternative algorithms

Below are the ones l have made but are being flagged as incorrect by the Online Judge on a coding website.

After declaring variable of int data type k, l received an input from the console using cin(). Since the constraints of the question read that the possible number(s) is/are between 1 and 20000, l first off opened a for loop using these conditions. At every iteration of i (one after the other), the number is tested whether its digits sum up to 10 and if they do, whether its the kth number whose digits are of sum 10.

To find the sum of digits, l used either a recursive function or an iterative method using a while loop. Hence the two snippets of codes. In both methods, the sum is calculated by finding the digits first using modular % operator and division operator /. The sum is figured out and then further tested if its equal to 10 and if Yes, it is also tested if its the K th element by means of keeping count of all previous similar elements. After all conditions are satisfied, only then is the value i outputted using cout().

#include <bits/stdc++.h>

using namespace std;

//recursion to get sum of digits.

*int sum(int d)

{

 return d==0?0:d%10+sum(d/10);

}*

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

    {

     int total=sum(i);

      if(total==10)

     {

      --k;

      if(k==0)

      cout<<i<<"\n";

      }

     }

  }

   return 0;

}

Second one, l used iterations(while loop) to deduce sum of digits

#include <bits/stdc++.h>

using namespace std;

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

{

     int sum=0,d=i;

     *while(d!=0)

       {

          sum+=d%10;

           d/=10;

       }*


     if(sum==10)

       {

         --k;

          if(k==0)

          cout<<i<<"\n";

        }
    }

 }

return 0;

}

So l need alternative algorithms of better efficiency. Thanks in advance

Answer 1

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;
}

Answer 2

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));

Answer 3

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;

     }

Answer 4

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.