Кратное 3 и 5:
Задача просит найти сумму всех кратных 3 и 5 меньше 1000.
Самый первый подход, который пришел мне в голову, заключался в том, чтобы перебрать числа от 1 до 1000 и суммировать те, которые делятся на 3 или 5.
Это можно наивно написать на Python следующим образом:
Это правильно, но выглядит некрасиво для такого красивого языка, как Python.
Пифоническую версию можно записать следующим образом:
sum (iterable, start): возвращает сумму start (по умолчанию 0) и элементов итераций.
Отлично. Всего лишь строчка кода!
Однако это требует линейной сложности, если предположить, что N (здесь = 1000) не является постоянным.
Это не очень хорошо, если у нас очень большие значения N и жесткие временные ограничения .
Мы можем решить эту проблему со сложностью O (1)!
- Сумма кратных (3 или 5) = Сумма кратных (3) + Сумма кратных (5) -Сумма кратных (15)
- Сумма кратных (n, r) = n * (r * (r + 1)) / 2 (с использованием арифметической прогрессии),
где n - число, кратное которому мы хотим, а r - количество кратные, которые нам необходимо учитывать.
Например:
Кратные 5 ниже 1000 составляют 5,10,15,20,… .,995 (n = 5, r = 199).
Answer: 233168
Не стесняйтесь комментировать сомнения или предложения.
