Dada una array con enteros positivos. La tarea es encontrar el factorial de todos los elementos del arreglo.
Nota : como los números serían muy grandes, imprímalos tomando un módulo con 10 9 +7.
Ejemplos:
Input: arr[] = {3, 10, 200, 20, 12}
Output: 6 3628800 722479105 146326063 479001600
Input: arr[] = {5, 7, 10}
Output: 120 5040 3628800
Enfoque ingenuo: sabemos que existe un enfoque simple para calcular el factorial de un número . Podemos ejecutar un ciclo para todos los valores de array y podemos encontrar el factorial de cada número utilizando el enfoque anterior.
La Complejidad del Tiempo sería O(N 2 )
La Complejidad del Espacio sería O(1)
Enfoque Eficiente: Sabemos que el factorial de un número:
N! = N*(N-1)*(N-2)*(N-3)*****3*2*1
La fórmula recursiva para calcular el factorial de un número es:
fact(N) = N*fact(N-1).
Por lo tanto, construiremos una array de forma ascendente utilizando la recursividad anterior. Una vez que hayamos almacenado los valores en la array, podemos responder las consultas en tiempo O (1). Por lo tanto, la complejidad temporal total sería O(N). Podemos usar este método solo si los valores de la array son inferiores a 10^6. De lo contrario, no podríamos almacenarlos en una array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007 ;
int SIZE = 10000;
// vector to store the factorial values
// max_element(arr) should be less than SIZE
vector<long> fact;
// Function to calculate the factorial
// using dynamic programming
void factorial()
{
int i;
fact.push_back((long)1);
for (i = 1; i <= SIZE; i++)
{
// Calculation of factorial
// As fact[i-1] stores the factorial of n-1
// so factorial of n is fact[i] = (fact[i-1]*i)
fact.push_back((fact[i - 1] * i) % MOD);
}
}
// Function to print factorial of every element
// of the array
void PrintFactorial(int arr[],int n)
{
for(int i = 0; i < n; i += 1)
{
// Printing the stored value of arr[i]!
cout << fact[arr[i]] << " ";
}
}
int main()
{
int arr[] = {3, 10, 200, 20, 12};
int n = sizeof(arr) / sizeof(arr[0]);
// Function to store factorial values mod 10**9+7
factorial();
// Function to print the factorial values mod 10**9+7
PrintFactorial(arr,n);
return 0;
}
// This code is contributed by decode2207.
Java
<script>
// Java implementation of the approach
import java.util.*;
class Sol
{
static int MOD = 1000000007 ;
static int SIZE = 10000;
// vector to store the factorial values
// max_element(arr) should be less than SIZE
static Vector<Long> fact = new Vector<Long>();
// Function to calculate the factorial
// using dynamic programming
static void factorial()
{
int i;
fact.add((long)1);
for (i = 1; i <= SIZE; i++)
{
// Calculation of factorial
// As fact[i-1] stores the factorial of n-1
// so factorial of n is fact[i] = (fact[i-1]*i)
fact.add((fact.get(i - 1) * i) % MOD);
}
}
// Function to print factorial of every element
// of the array
static void PrintFactorial(int arr[],int n)
{
for(int i = 0; i < n; i += 1)
{
// Printing the stored value of arr[i]!
System.out.print(fact.get(arr[i])+" ");
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {3, 10, 200, 20, 12};
int n = arr.length;
// Function to store factorial values mod 10**9+7
factorial();
// Function to print the factorial values mod 10**9+7
PrintFactorial(arr,n);
}
}
// This code is contributed by Arnab Kundu
</script>
Python3
# Python implementation of the above Approach mod = 1000000007 SIZE = 10000 # declaring list initially and making # it 1 i.e for every index fact = [1]*SIZE # Calculation of factorial using Dynamic programming def factorial(): for i in range(1, SIZE): # Calculation of factorial # As fact[i-1] stores the factorial of n-1 # so factorial of n is fact[i] = (fact[i-1]*i) fact[i] = (fact[i-1]*i) % mod # function call factorial() # Driver code arr=[3,10,200,20,12] for i in arr: print(fact[i])
PHP
<?php
// PHP implementation of the approach
$MOD = 1000000007 ;
$SIZE = 10000 ;
// Function to calculate the factorial
// using dynamic programming
function factorial($fact)
{
$fact[0] = 1;
for ($i = 1; $i <= $GLOBALS['SIZE']; $i++)
{
// Calculation of factorial
// As fact[i-1] stores the factorial of n-1
// so factorial of n is fact[i] = (fact[i-1]*i)
$fact[$i] = ($fact[$i - 1] * $i) % $GLOBALS['MOD'];
}
return $fact;
}
// Function to print factorial of every element
// of the array
function PrintFactorial($fact, $arr, $n)
{
for($i = 0; $i < $n; $i++)
{
// Printing the stored value of arr[i]!
echo $fact[$arr[$i]]," ";
}
}
// Driver code
// vector to store the factorial values
// max_element(arr) should be less than SIZE
$fact = array_fill(0,$SIZE + 1, 0);
$arr = array(3, 10, 200, 20, 12);
$n = count($arr);
// Function to store factorial values mod 10**9+7
$fact = factorial($fact);
// Function to print the factorial values mod 10**9+7
PrintFactorial($fact,$arr,$n);
// This code is contributed by AnkitRai01
?>
C#
// C# implementation of above approach
using System.Collections.Generic;
using System;
class Sol
{
static int MOD = 1000000007 ;
static int SIZE = 10000;
// vector to store the factorial values
// max_element(arr) should be less than SIZE
static List<long> fact = new List<long>();
// Function to calculate the factorial
// using dynamic programming
static void factorial()
{
int i;
fact.Add((long)1);
for (i = 1; i <= SIZE; i++)
{
// Calculation of factorial
// As fact[i-1] stores the factorial of n-1
// so factorial of n is fact[i] = (fact[i-1]*i)
fact.Add((fact[i - 1] * i) % MOD);
}
}
// Function to print factorial of every element
// of the array
static void PrintFactorial(int []arr,int n)
{
for(int i = 0; i < n; i += 1)
{
// Printing the stored value of arr[i]!
Console.Write(fact[arr[i]]+" ");
}
}
// Driver code
public static void Main(String []args)
{
int []arr = {3, 10, 200, 20, 12};
int n = arr.Length;
// Function to store factorial values mod 10**9+7
factorial();
// Function to print the factorial values mod 10**9+7
PrintFactorial(arr,n);
}
}
// This code is contributed by 29AjayKumar
Javascript
// Javascript implementation of the approach
let MOD = 1000000007;
let SIZE = 10000;
// Function to calculate the factorial
// using dynamic programming
function factorial(fact)
{
fact[0] = 1;
for (let i = 1; i <= SIZE; i++)
{
// Calculation of factorial
// As fact[i-1] stores the factorial of n-1
// so factorial of n is fact[i] = (fact[i-1]*i)
fact[i] = (fact[i - 1] * i) % MOD;
}
return fact;
}
// Function to print factorial of every element
// of the array
function PrintFactorial(fact, arr, n)
{
for(let i = 0; i < n; i++)
{
// Printing the stored value of arr[i]!
document.write(fact[arr[i]] + " ");
}
}
// Driver code
// vector to store the factorial values
// max_element(arr) should be less than SIZE
let fact = new Array(SIZE + 1).fill(0);
let arr = new Array(3, 10, 200, 20, 12);
let n = arr.length;
// Function to store factorial values mod 10**9+7
fact = factorial(fact);
// Function to print the factorial values mod 10**9+7
PrintFactorial(fact,arr,n);
// This code is contributed by gfgking
Producción:
6 3628800 722479105 146326063 479001600
Complejidad de tiempo : O(N)
Complejidad de espacio : O(N)
Publicación traducida automáticamente
Artículo escrito por YashKhandelwal8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA