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

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!

CodePudding user response：

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

CodePudding user response：

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