Factoriales de prefijos de una array de suma de prefijos

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar los factoriales de prefijos de una array de suma de prefijos de la array dada, es decir, $prefix[i] = (\sum_{0}^{i}arr[i])!$ .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4}
Salida: 1 6 720 3628800
Explicación:
La suma del prefijo de la array dada es {1, 3, 6, 10}. Por lo tanto, los factoriales de prefijos de la array de suma de prefijos obtenida son {1!, (1+2)!, (1+2+3)!, (1+2+3+4)!} = {1!, 3!, 6!, 10!} = {1 6 720 3628800}.

Entrada: arr[] = {2, 4, 3, 1}
Salida: 2 720 362880 3628800

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar la suma de prefijos de la array dada y luego encontrar el factorial de cada elemento de la array en la array de suma de prefijos. Después de calcular la suma del prefijo, imprima la array factorial.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the factorial of
// a number N
int fact(int N)
{
    // Base Case
    if (N == 1 || N == 0)
        return 1;
 
    // Find the factorial recursively
    return N * fact(N - 1);
}
 
// Function to find the prefix
// factorial array
void prefixFactorialArray(int arr,
                          int N)
{
    // Find the prefix sum array
    for (int i = 1; i < N; i++) {
        arr[i] += arr[i - 1];
    }
 
    // Find the factorials of each
    // array element
    for (int i = 0; i < N; i++) {
        arr[i] = fact(arr[i]);
    }
 
    // Print the resultant array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    prefixFactorialArray(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to find the factorial of
// a number N
static int fact(int N)
{
     
    // Base Case
    if (N == 1 || N == 0)
        return 1;
 
    // Find the factorial recursively
    return N * fact(N - 1);
}
 
// Function to find the prefix
// factorial array
static void prefixFactorialArray(int[] arr, int N)
{
 
    // Find the prefix sum array
    for(int i = 1; i < N; i++)
    {
        arr[i] += arr[i - 1];
    }
 
    // Find the factorials of each
    // array element
    for(int i = 0; i < N; i++)
    {
        arr[i] = fact(arr[i]);
    }
 
    // Print the resultant array
    for(int i = 0; i < N; i++)
    {
        System.out.print(arr[i] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.length;
 
    prefixFactorialArray(arr, N);
}
}
 
// This code is contributed by ukasp

Python3

# Python implementation of the approach
def fact(N):
   
    # Base Case
    if (N == 1 or N == 0):
        return 1
 
    # Find the factorial recursively
    return N * fact(N - 1)
 
 
# Function to find the prefix
# factorial array
def prefixFactorialArray(arr, N):
 
    # Find the prefix sum array
    for i in range(1, N):
        arr[i] += arr[i - 1]
 
    # Find the factorials of each
    # array element
    for i in range(N):
        arr[i] = fact(arr[i])
 
        # Print the resultant array
    for i in range(N):
        print(arr[i], end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 3, 4]
    N = len(arr)
    prefixFactorialArray(arr, N)
 
# This code is contributed by kirtishsurangalikar

C#

// C# program for the above approach
using System;
         
class GFG{
 
// Function to find the factorial of
// a number N
static int fact(int N)
{
     
    // Base Case
    if (N == 1 || N == 0)
        return 1;
 
    // Find the factorial recursively
    return N * fact(N - 1);
}
 
// Function to find the prefix
// factorial array
static void prefixFactorialArray(int[] arr,
                                 int N)
{
     
    // Find the prefix sum array
    for(int i = 1; i < N; i++)
    {
        arr[i] += arr[i - 1];
    }
 
    // Find the factorials of each
    // array element
    for(int i = 0; i < N; i++)
    {
        arr[i] = fact(arr[i]);
    }
 
    // Print the resultant array
    for(int i = 0; i < N; i++)
    {
        Console.Write(arr[i] + " ");
    }
}
     
// Driver Code
public static void Main()
{
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
     
    prefixFactorialArray(arr, N);
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the factorial of
// a number N
function fact(N) {
    // Base Case
    if (N == 1 || N == 0)
        return 1;
 
    // Find the factorial recursively
    return N * fact(N - 1);
}
 
// Function to find the prefix
// factorial array
function prefixFactorialArray(arr, N) {
    // Find the prefix sum array
    for (let i = 1; i < N; i++) {
        arr[i] += arr[i - 1];
    }
 
    // Find the factorials of each
    // array element
    for (let i = 0; i < N; i++) {
        arr[i] = fact(arr[i]);
    }
 
    // Print the resultant array
    for (let i = 0; i < N; i++) {
        document.write(arr[i] + " ");
    }
}
 
// Driver Code
 
let arr = [1, 2, 3, 4];
let N = arr.length;
prefixFactorialArray(arr, N);
 
</script>

Producción:

1 6 720 3628800

Complejidad de tiempo: O(N*M), donde M es la suma de los elementos de la array .
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar precalculando el factorial de la suma de los elementos de la array para que el cálculo factorial en cada índice se pueda calcular en tiempo O(1) .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the factorial of
// prefix sum at every possible index
void prefixFactorialArray(int A[], int N)
{
    // Find the prefix sum array
    for (int i = 1; i < N; i++) {
        A[i] += A[i - 1];
    }
 
    // Stores the factorial of all the
    // element till the sum of array
    int fact[A[N - 1] + 1];
    fact[0] = 1;
 
    // Find the factorial array
    for (int i = 1; i <= A[N - 1]; 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]);
    prefixFactorialArray(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to find the factorial of
// prefix sum at every possible index
static void prefixFactorialArray(int A[], int N)
{
     
    // Find the prefix sum array
    for(int i = 1; i < N; i++)
    {
        A[i] += A[i - 1];
    }
 
    // Stores the factorial of all the
    // element till the sum of array
    int fact[] = new int[A[N - 1] + 1];
    fact[0] = 1;
 
    // Find the factorial array
    for(int i = 1; i <= A[N - 1]; 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;
     
    prefixFactorialArray(arr, N);
}
}
 
// This code is contributed by abhinavjain194

Python3

# // python program for the above approach
 
# // Function to find the factorial of
# // prefix sum at every possible index
def prefixFactorialArray(A, N):
   
    # // Find the prefix sum array
    for i in range(1, N):
        A[i] += A[i - 1]
 
    # // Stores the factorial of all the
    # // element till the sum of array
    fact = [0 for x in range(A[N - 1] + 1)]
    fact[0] = 1
 
    # // Find the factorial array
    for i in range(1, A[N-1]+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
arr = [1, 2, 3, 4]
N = len(arr)
prefixFactorialArray(arr, N)
 
# This code is contributed by amreshkumar3.

C#

// C# program for the above approach
using System;
class GFG {
     
    // Function to find the factorial of
    // prefix sum at every possible index
    static void prefixFactorialArray(int[] A, int N)
    {
          
        // Find the prefix sum array
        for(int i = 1; i < N; i++)
        {
            A[i] += A[i - 1];
        }
      
        // Stores the factorial of all the
        // element till the sum of array
        int[] fact = new int[A[N - 1] + 1];
        fact[0] = 1;
      
        // Find the factorial array
        for(int i = 1; i <= A[N - 1]; 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
  static void Main() {
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
      
    prefixFactorialArray(arr, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
 
// Javascript program for the above approach
 
 
// Function to find the factorial of
// prefix sum at every possible index
function prefixFactorialArray(A, N) {
    // Find the prefix sum array
    for (let i = 1; i < N; i++) {
        A[i] += A[i - 1];
    }
 
    // Stores the factorial of all the
    // element till the sum of array
    let fact = new Array(A[N - 1] + 1);
    fact[0] = 1;
 
    // Find the factorial array
    for (let i = 1; i <= A[N - 1]; 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
prefixFactorialArray(arr, N);
 
// This code is contributed by _saurabh_jaiswal.
</script>

Producción:

1 6 720 3628800

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

Publicación traducida automáticamente

Artículo escrito por devro3014 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta