Префиксные факториалы массива префиксных сумм

Учитывая массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти префиксные факториалы массива префиксных сумм данного массива, т.е. .

Примеры:

Input: arr[] = {1, 2, 3, 4}
Output: 1 6 720 3628800
Explanation:
The prefix sum of the given array is {1, 3, 6, 10}. Therefore, prefix factorials of the obtained prefix sum array is {1!, (1+2)!, (1+2+3)!, (1+2+3+4)!} = {1!, 3!, 6!, 10!} = {1 6 720 3628800}.

Input: arr[] = {2, 4, 3, 1}
Output: 2 720 362880 3628800
 

Наивный подход: самый простой подход к решению данной проблемы - найти сумму префиксов данного массива, а затем найти факториал каждого элемента массива в массиве суммы префиксов. После вычисления суммы префикса выведите факторный массив.

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

Выход:

1 6 720 3628800 

Временная сложность: O(N*M), где M — сумма элементов массива .
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать путем предварительного вычисления факториала суммы элементов массива, чтобы вычисление факториала для каждого индекса можно было выполнить за время O(1) .

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

Временная сложность: O(N + M), где M — сумма элементов массива .
Вспомогательное пространство: O(M), где M — сумма элементов массива .