Как определить числа в составе списка, сумма цифр которых равна N?

Дан список, состоящий из чисел от 1 до 1000. Необходимо определить все числа, цифры которых в сумме дают 13 (67, 76, 931 и т.д.). Понимаю, как это реализовать, если бы было дано одно число (1000, скажем), но в рамках списка непонятно. Пробуй следующий код, но безрезультатно:

n=[i for i in range(1001)]
res=[0 for k in range(1001)]
for i in n:
    while i:
        a=i%10
        i=i//10
        res[k]+=a
        if res[k] == 13:
            print(i)

Ответы (3 шт):

Автор решения: MBo

res делайте просто числом, не массивом, обнуляйте на каждой итерации. На каждой итерации копируйте i в t, и далее работайте с t, чтобы счётчик цикла не менять

n=[i for i in range(1001)]
# или просто for i in range(1001): ?
for i in n:
    t = i
    res = 0
    while t:
        res += t%10
        t //= 10
    if res == 13:
        print(i)

Если диапазон будет больше, то стоит подумать об оптимизации - не проверять все числа, а просто генерировать те числа, для которых сумма цифр равна требуемой

→ Ссылка
Автор решения: CrazyElf

Просто как ещё один вариант эта задача решается короче с использованием встроенных функций питона (но менее оптимально, поскольку работа со строками медленнее, чем работа с числами):

for i in range(1001):
    if sum(map(int, str(i))) == 13:
        print(i)

Или даже в одну строку тот же по сути код:

print(*(i for i in range(1001) if sum(map(int, str(i))) == 13), sep='\n')

Или другой однострочник:

print(*filter(lambda x: sum(map(int, str(x))) == 13, range(1001)), sep='\n')
→ Ссылка
Автор решения: Stanislav Volodarskiy

А ведь отличная задача!

Перебор и проверка хорошо работают для небольших n, но можно заметить, что чисел с суммой цифр тринадцать немного. Если в числе ровно k разрядов, то таких чисел не более Сk+1112, что составляет лишь (бесконечно) малую долю от общего количества чисел 9·10k-1. А раз так, то их надо уметь находить без последовательного перебора всех чисел.

Конструировать числа будем последовательно увеличивая их разрядность k - генератор search(k, s, n, d1). Сами числа конструируются от старших разрядов к младшим. При добавлении разряда обновляется s - доступный остаток суммы цифр и n - само число.

Генератор search бесконечный, последовательно вызывает search(k, ...) увеличивая k. Функция main останавливает его, когда очередное число превысило порог.

def search(ss):

    def search(k, s, n, d1):
        if k == 0:
            yield n

        min_d = max(d1, s - 9 * (k - 1))
        max_d = min(9, s)
        for d in range(min_d, max_d + 1):
            yield from search(k - 1, s - d, 10 * n + d, 0)

    k = 1
    while True:
        yield from search(k, ss, 0, 1)
        k += 1


def main():
    s, n = map(int, input().split())
    for i in search(s):
        if i > n:
            break
        print(i)


main()
$ time echo 13 1_000 | python temp.py | wc -l
75

real  0m0.030s
user  0m0.028s
sys   0m0.000s

Прогоны для суммы цифр - тринадцать:

n время работы количество чисел
103 0.03 с 75
104 0.03 с 480
105 0.04 с 2205
106 0.05 с 8232
107 0.1 с 26544
108 0.3 с 76560
109 0.6 с 202005
1010 1.5 с 495220
1011 3.5 с 1140920
1012 8.0 с 2491776
1013 17.3 с 5194385
1014 35.7 с 10392760
1015 71.0 с 20048100
1016 143 с 37429104
1017 311 с 67847442
1018 510 с 119739330
→ Ссылка