Prefix Factorials of a Prefix Sum Array

Given an array arr[] consisting of N positive integers, the task is to find the prefix factorials of a prefix sum array of the given array i.e., .

Examples:

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
 

Naive Approach: The simplest approach to solve the given problem is to find the prefix sum of the given array and then find the factorial of each array element in the prefix sum array. After calculating the prefix sum print the factorial array.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h> using namespace std;    int fact(int N) {          if (N == 1 || N == 0)         return 1;             return N * fact(N - 1); }    void prefixFactorialArray(int arr,                           int N) {          for (int i = 1; i < N; i++) {         arr[i] += arr[i - 1];     }                  for (int i = 0; i < N; i++) {         arr[i] = fact(arr[i]);     }             for (int i = 0; i < N; i++) {         cout << arr[i] << " ";     } }    int main() {     int arr[] = { 1, 2, 3, 4 };     int N = sizeof(arr) / sizeof(arr[0]);     prefixFactorialArray(arr, N);        return 0; }

Output:

1 6 720 3628800

Time Complexity: O(N*M), where M is the sum of the array elements. 
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by precalculating the factorial of sum of the array elements so that the factorial calculation at each index is can be calculated in O(1) time.

Below is an implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void prefixFactorialArray(int A[], int N) {          for (int i = 1; i < N; i++) {         A[i] += A[i - 1];     }                  int fact[A[N - 1] + 1];     fact[0] = 1;             for (int i = 1; i <= A[N - 1]; i++) {         fact[i] = i * fact[i - 1];     }                  for (int i = 0; i < N; i++) {         A[i] = fact[A[i]];     }             for (int i = 0; i < N; i++) {         cout << A[i] << " ";     } }    int main() {     int arr[] = { 1, 2, 3, 4 };     int N = sizeof(arr) / sizeof(arr[0]);     prefixFactorialArray(arr, N);        return 0; }

Output:

1 6 720 3628800

Time Complexity: O(N + M), where M is the sum of the array elements.
Auxiliary Space: O(M), where M is the sum of the array elements.

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets