Given an array arr[] consisting of N positive integers, the task is to find the suffix factorials of a suffix sum array of the given array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: {3628800, 362880, 5040, 24}
Explanation: The suffix sum of the given array is {10, 9, 7, 4}.
Therefore, suffix factorials of the obtained suffix sum array is {10!, 9!, 7!, 4!}Input: arr[] = {2, 0}
Output: {2, 1}
Approach: The task can be solved by pre-calculating the factorials of all numbers till the entire sum of the array. So that the factorial calculation at each index of the suffix sum array is can be calculated in unit time.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the factorial of// suffix sum at every possible indexvoid suffixFactorialArray(int A[], int N){ // Find the suffix sum array for (int i = N - 2; i >= 0; i--) { A[i] += A[i + 1]; } // Stores the factorial of all the // element till the sum of array int fact[A[0] + 1]; fact[0] = 1; // Find the factorial array for (int i = 1; i <= A[0]; i++) { fact[i] = i * fact[i - 1]; } // Find the factorials of // each array element for (int i = 0; i < N; i++) { A[i] = fact[A[i]]; } // Print the resultant array for (int i = 0; i < N; i++) { cout << A[i] << " "; }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); suffixFactorialArray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;public class GFG { // Function to find the factorial of // suffix sum at every possible index static void suffixFactorialArray(int[] A, int N) { // Find the suffix sum array for (int i = N - 2; i >= 0; i--) { A[i] += A[i + 1]; } // Stores the factorial of all the // element till the sum of array int[] fact = new int[A[0] + 1]; fact[0] = 1; // Find the factorial array for (int i = 1; i <= A[0]; i++) { fact[i] = i * fact[i - 1]; } // Find the factorials of // each array element for (int i = 0; i < N; i++) { A[i] = fact[A[i]]; } // Print the resultant array for (int i = 0; i < N; i++) { System.out.print(A[i] + " "); } } // Driver Code public static void main(String args[]) { int[] arr = { 1, 2, 3, 4 }; int N = arr.length; suffixFactorialArray(arr, N); }}// This code is contributed by Saurabh Jaiswal |
Python3
# python3 program for the above approach# Function to find the factorial of# suffix sum at every possible indexdef suffixFactorialArray(A, N): # Find the suffix sum array for i in range(N-2, -1, -1): A[i] += A[i + 1] # Stores the factorial of all the # element till the sum of array fact = [0 for _ in range(A[0] + 1)] fact[0] = 1 # Find the factorial array for i in range(1, A[0] + 1): fact[i] = i * fact[i - 1] # Find the factorials of # each array element for i in range(0, N): A[i] = fact[A[i]] # Print the resultant array for i in range(0, N): print(A[i], end=" ")# Driver Codeif __name__ == "__main__": arr = [1, 2, 3, 4] N = len(arr) suffixFactorialArray(arr, N)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the factorial of // suffix sum at every possible index static void suffixFactorialArray(int []A, int N) { // Find the suffix sum array for (int i = N - 2; i >= 0; i--) { A[i] += A[i + 1]; } // Stores the factorial of all the // element till the sum of array int []fact = new int[A[0] + 1]; fact[0] = 1; // Find the factorial array for (int i = 1; i <= A[0]; i++) { fact[i] = i * fact[i - 1]; } // Find the factorials of // each array element for (int i = 0; i < N; i++) { A[i] = fact[A[i]]; } // Print the resultant array for (int i = 0; i < N; i++) { Console.Write(A[i] + " "); } } // Driver Code public static void Main() { int []arr = { 1, 2, 3, 4 }; int N = arr.Length; suffixFactorialArray(arr, N); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the factorial of // suffix sum at every possible index function suffixFactorialArray(A, N) { // Find the suffix sum array for (let i = N - 2; i >= 0; i--) { A[i] += A[i + 1]; } // Stores the factorial of all the // element till the sum of array let fact = new Array(A[0] + 1); fact[0] = 1; // Find the factorial array for (let i = 1; i <= A[0]; i++) { fact[i] = i * fact[i - 1]; } // Find the factorials of // each array element for (let i = 0; i < N; i++) { A[i] = fact[A[i]]; } // Print the resultant array for (let i = 0; i < N; i++) { document.write(A[i] + " "); } } // Driver Code let arr = [1, 2, 3, 4]; let N = arr.length; suffixFactorialArray(arr, N); // This code is contributed by Potta Lokesh </script> |
Output
3628800 362880 5040 24
Time Complexity: O(N + M), where M is the sum of array elements.
Auxiliary Space: O(M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
