Найдите сумму факториалов до N факториала (1! + 2! + 3! + … + N!)

Опубликовано: 20 Сентября, 2022

Дано положительное целое число N . Задача состоит в том, чтобы вычислить сумму факториала от 1! к Н!, 1! + 2! + 3! + … + Н! .

Примеры :

Input: N = 5
Output: 153
Explanation: 1! + 2! + 3! + 4! + 5! = 1 + 2 + 6 + 24 + 120 = 153.

Input: N = 1
Output: 1

Наивный подход : основной способ решить эту задачу — найти факториал всех чисел от 1 до N и вычислить их сумму.
Временная сложность : O(N^2)
Вспомогательное пространство : O(1)

Подход . Эффективным подходом является вычисление факториала и суммы в одном и том же цикле, что составляет время O(N). Пройдите числа от 1 до N и для каждого числа i:

  • Умножьте i на предыдущий факториал (изначально 1).
  • Добавьте этот новый факториал к общей сумме

В конце выведите эту общую сумму.

Ниже приведена реализация описанного выше подхода.


Временная сложность : O(N)
Вспомогательное пространство : O(1), так как дополнительное пространство не занято.

РЕКОМЕНДУЕМЫЕ СТАТЬИ