Encuentre los factoriales de sufijos de una array de suma de sufijos de la array dada

arreglo array [] N

Ejemplos:

Entrada : arr[] = {1, 2, 3, 4}
Salida : {3628800, 362880, 5040, 24}
Explicación :

Entrada : arr[] = {2, 0}
Salida : {2, 1}

Enfoque : la tarea se puede resolver calculando previamente los factoriales de todos los números hasta la suma total de la array . Para que el .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the factorial of
// suffix sum at every possible index
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[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 Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    suffixFactorialArray(arr, N);
    return 0;
}

// Java program for the above approach
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 program for the above approach
 
# Function to find the factorial of
# suffix sum at every possible index
def 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 Code
if __name__ == "__main__":
 
    arr = [1, 2, 3, 4]
    N = len(arr)
 
    suffixFactorialArray(arr, N)
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using 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.

<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>

3628800 362880 5040 24 

Complejidad temporal: O(N + M), donde M es la suma de los elementos de la array.
Espacio Auxiliar: O(M)