Find count of N-digits numbers which consist of digits give you the sum is equal to K. Return count, the smallest and the largest number

Question

I am finding for the effecient solution on that task
You are given K is summ of digits are in number and N is count of digits in the number.
So you have to find count of all numbers, the smallest number and the largest number.
Also It has to be sorted number. For example:

145 - sorted number, because 4 > 1, and 5 > 4.
382 - not sorted number, because 3 < 8, but 8 > 2.

Everything must correspond to the condition of the problem.
Here is what I did:

def find_all(sum_dig, digs):
    min_num = 10000000000000000
    max_num = -1
    count = 0
    for i in range((10 ** digs // 10), 10 ** digs):
        summ = 0
        for j in range(len(str(i))):
            summ += int((str(i))[j])
        if summ == sum_dig and str(i) == ''.join(sorted(str(i))):
            count += 1
            if i > max_num:
                max_num = i
            if i < min_num:
                min_num = i

    if count == 0:
        return []
    else:
        return [count, min_num, max_num]

But that code works pretty slow, I get the error Execution Timed Out (12000 ms)
Could you tell is there any way to make it more effecient?
Any advices are appreciated!

Answer 1

find all numbers which give you the sum equal to s

m, s = map(int, input('').split(' ')) # m: length , s : sum of digits
result = []

counter = 0
def getSum(n):
    sum = 0
    while (n != 0):
        sum = sum + (n % 10)
        n = n // 10
    return sum


for i in range((10 ** (m - 1)), (10 ** m)):
    r = getSum(i)
    if r == s:
       counter += 1
       result.append(i)

print(counter, result)

Answer 2

Here's my take with a function for each value required, which seems to pass the tests (when returning an empty list if the partition count is zero).

For the number of results, we can modify the recursion for partitions with restricted number of parts: take (1) the count of all partitions of n-k into k parts that have largest part at most l-1 and add to them (2) the count of all partitions of n-1 into k-1 parts that have largest part at most l. (For each part in (1) add 1, for a total of k 1s. For each partition in (2), add a part 1.) O(n, k) search space.

def f(n, k, l, memo={}):
  if k == 0 and n == 0:
    return 1

  if n <= 0 or k <= 0 or l <= 0:
    return 0

  if (n, k, l) in memo:
    return memo[(n, k, l)]

  memo[(n, k, l)] = f(n - k, k, l-1, memo) + f(n - 1, k - 1, l, memo)

  return memo[(n, k, l)]

For the smallest, we can use a greedy O(n) approach from left to right, always picking the smallest possible digit.

def g(n, k):
  if k == 0:
    return 0

  next_digit = max(1, n - 9 * (k - 1))

  return next_digit * 10 ** (k - 1) + g(n - next_digit, k - 1)

For the largest, I couldn't think of a better approach than a recursion that limits the choice for the digit based on the current state. O(n, k). bb1 commented an O(n) solution for this one.

from math import ceil

def h(n, k, largest):
  if n < 0:
    return 0

  if k == 1:
    return n

  best = 0
  digit = 0
  
  for i in range(
    min(largest, n - k + 1),
    min(largest, ceil(n / k)) - 1,
    -1):
    candidate = h(n - i, k - 1, i)
    if candidate > best:
      best = candidate
      digit = i

  return digit + 10 * best

Answer 3

You could use a recursive approach that collects 1 digit at a time into a list until it reaches the specified total returning the value if its sum matches correctly. Then we can make heavy use of filtering to avoid testing numbers that we know will either exceed the target sum or are not in increasing order, cutting down the potential amount of values we have to check significantly.

I tested on the website and it does pass all tests within the allotted time.

The find_all function merely takes the result and puts it into the format required by the challenge.

def find_all(sum_dig, digs):
    result = find_count(sum_dig, digs, [])
    size, sm, lg = len(result), min(result), max(result)
    return [size, sm, lg]


def find_count(sum_dig, digs, lst=[]):
    if len(lst) == digs:
        if sum(lst) == sum_dig:
            return [int(''.join([str(i) for i in lst]))]
        return []
    combos = []
    start = 1 if not len(lst) else lst[-1]
    for i in range(start, 10):
        t = 0 if not lst else sum(lst)
        if t + i <= total:
            combos += find_count(sum_dig, digs, lst + [i])
    return combos

Answer 4

Rather than iterating for every number from 10^(digs-1) until 10^digs, which will have a broad search space, we can iterate by adding the digit in a non-decreasing manner one by one from the leftmost digit to the rightmost digit (or non-increasing manner from right to left if you prefer it). Reference

I tested the python code below on the site and it seems to solve the task.

I think the time complexity of this code can still be improved.

You can try searching about top-down dynamic programming and memoization technique if you want to optimize it.

def find_all(sum_dig, digs):
    global total_count, lowest_value, greatest_value
    
    total_count = 0
    lowest_value = -1
    greatest_value = -1
    
    # complete search via depth first search
    def dfs(digit_sum, digit_count, num, digit_from):
        global total_count, lowest_value, greatest_value
        
        # base case
        if digit_count == digs:
            if digit_sum == sum_dig:
                if lowest_value == -1:
                    lowest_value = num
                greatest_value = num
                total_count += 1
            return
        
        # try all possible values one by one
        for i in range(digit_from, 10):
            dfs(digit_sum + i, digit_count + 1, num * 10 + i, i)
    
    dfs(0, 0, 0, 1)
    
    answer = []
    if total_count > 0:
        answer = [total_count, lowest_value, greatest_value]
    return answer