Find the kth smallest number whose sum equals m

Question

Example of what I am looking for:

Input: M = 5, K = 3
Output: 23
Sequence of numbers starting from 1 with digit sum as 5 is as follows:
5
14
23
32
41
So 3rd smallest number is 23

My approach, it gives me what I am looking for, but I don't think this is the optimal way to do it. A lot of unnecessary calculations are taking place when K>1. In my solution, I am referring M as num and K as position.

def kthsmallest(num, position):
    pos=1

    #return first or you can say minimum number whose sum of digits is equal to num when k=1 or 0
    if position == 0:
        return 0
    if position ==1:
        return str(num % 9) + ('9' * (num//9))

    #when given kth position is more than 1
    if position >1:
        i =num

    while True:

        #Inilitize sum =0 and on each iteration it will set 0
        sum = 0

        #Calculate sum of digits in number i
        for digit in str(i):
            sum = sum+ int(digit)

        #Check if sum of digits is equal to number given
        if sum ==num:
           if pos == position:
               return i
           pos +=1
        i +=1

print(kthsmallest(21,2))

Can somebody help me to refactor the code? or can suggest a completely new approach to do it. Please comment if more info required.

Lord Elrond · Accepted Answer · 2020-02-25T04:33:36.630

I don't think this is the most optimal solution, but it is an improvement, at least:

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

def kthsmallest(m, k):
    position = 1
    number = m

    while True:
        if sum_digits(number) == m:
            if position == k:
                return number
            position += 1
        number += 1

timeit results:

# new
> timeit.timeit('kthsmallest(5, 3)', setup=...)
7.015244078

# original
> timeit.timeit('kthsmallest(5, 3)', setup=...)
15.881711267

this is still painfully slow for larger values of m:

# new
> timeit.timeit('kthsmallest(21, 2)', setup=...)
224.548481592

# original
> timeit.timeit('kthsmallest(21, 2)', setup=...)
500.195695622

Credit to this answer for the sum_digits function.

score 1 · Answer 2 · answered Feb 25 '20 at 05:22

This is a very crude improvement on the already provided answer by @Reinstate Monica.

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

def kthsmallest(m, k):
    position = 1
    number = m
    found = False

    while True:
      if sum_digits(number) == m:
        if position == k:
          return number
        position += 1
        number += 9
        found = True
      elif found:
        number += 81
        found = False
      else:
        number += 1
"""

print(timeit.timeit('kthsmallest(5, 3)', setup=setup1))
print(timeit.timeit('kthsmallest(21, 2)', setup=setup1))

On my system this was the time taken for the two timeit calls -

λ test.py
1.0293785
142.652913

It is a slight speedup but will significantly slowdown once you look for even higher digit sums in numbers since we have basically hardcoded which numbers to skip based on a few known number properties. (This takes a while using timeit but was almost instant when I ran the code as is)

timeit takes the `number` argument (`100000` by default), which is the number of tests to run, hence your timeit test taking longer than running the code as is. — Lord Elrond, Feb 25 '20 at 05:27
@ReinstateMonica i forgot about the default being that large :| I assumed it was a much smaller number — Karan Shishoo, Feb 25 '20 at 05:28

Find the kth smallest number whose sum equals m

2 Answers2