Dado un número entero N , la tarea es encontrar el valor de la expresión ( N 1 * (N – 1) 2 * … * 1 N ) % (10 9 + 7) .
Entrada: N = 1
Salida: 1
Explicación:
1 1 = 1Entrada: N = 4
Salida: 288
Explicación:
4 1 * (4 – 1) 2 * (4 – 2) 3 * (4-3) 4
= 4 * 9 * 8 * 1
= 288
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [1, N] . Para cada i -ésima iteración, calcule el valor de (N – i + 1) i . Finalmente, imprima el producto de todos los valores calculados de cada iteración.
Complejidad de Tiempo: O(N 2 * log 2 (N))
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
F(N) = norte 1 * (N – 1) 2 * … * 1 N
= norte * (N – 1) * (N – 1) * (N – 2) * (N – 2) * (N – 2 )* … 1 * 1 * 1
= N * (N – 1) * (N – 2)*… * 1 * (N -1) * (N – 2) * …* 1 * …
= N! * (N-1)! * (N – 2)! * … * 1!
Siga los pasos a continuación para resolver el problema:
- Calcule previamente el valor del factorial de 1 a N usando factorial(N) = N * factorial(N – 1) .
- Iterar sobre el rango [1, N] y encontrar el producto de todos los factoriales sobre el rango [1, N] usando las observaciones anteriores
- Finalmente, imprima el valor de la expresión.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
// Function to find the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
int ValOfTheExpression(int n)
{
// factorial[i]: Stores factorial of i
int factorial[n] = { 0 };
// Base Case for factorial
factorial[0] = factorial[1] = 1;
// Precompute the factorial
for (int i = 2; i <= n; i++) {
factorial[i] = ((factorial[i - 1] % mod)
* (i % mod))
% mod;
}
// dp[N]: Stores the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
int dp[n] = { 0 };
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// Update dp[i]
dp[i] = ((dp[i - 1] % mod)
* (factorial[i] % mod))
% mod;
}
// Return the answer.
return dp[n];
}
// Driver Code
int main()
{
int n = 4;
// Function call
cout << ValOfTheExpression(n) << "\n";
}
Java
// Java program to implement
// the above approach
class GFG
{
static int mod = 1000000007;
// Function to find the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
static int ValOfTheExpression(int n)
{
// factorial[i]: Stores factorial of i
int[] factorial = new int[n + 1];
// Base Case for factorial
factorial[0] = factorial[1] = 1;
// Precompute the factorial
for (int i = 2; i <= n; i++)
{
factorial[i] = ((factorial[i - 1] % mod)
* (i % mod)) % mod;
}
// dp[N]: Stores the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
// Update dp[i]
dp[i] = ((dp[i - 1] % mod)
* (factorial[i] % mod)) % mod;
}
// Return the answer.
return dp[n];
}
// Driver code
public static void main(String[] args) {
int n = 4;
// Function call
System.out.println(ValOfTheExpression(n));
}
}
// This code is contributed by divyesh072019
Python3
# Python 3 program to implement # the above approach mod = 1000000007 # Function to find the value of the expression # ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7). def ValOfTheExpression(n): global mod # factorial[i]: Stores factorial of i factorial = [0 for i in range(n + 1)] # Base Case for factorial factorial[0] = 1 factorial[1] = 1 # Precompute the factorial for i in range(2, n + 1, 1): factorial[i] = ((factorial[i - 1] % mod) * (i % mod))%mod # dp[N]: Stores the value of the expression # ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7). dp = [0 for i in range(n+1)] dp[1] = 1 for i in range(2, n + 1, 1): # Update dp[i] dp[i] = ((dp[i - 1] % mod)*(factorial[i] % mod)) % mod # Return the answer. return dp[n] # Driver Code if __name__ == '__main__': n = 4 # Function call print(ValOfTheExpression(n)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
static int mod = 1000000007;
// Function to find the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
static int ValOfTheExpression(int n)
{
// factorial[i]: Stores factorial of i
int[] factorial = new int[n + 1];
// Base Case for factorial
factorial[0] = factorial[1] = 1;
// Precompute the factorial
for (int i = 2; i <= n; i++)
{
factorial[i] = ((factorial[i - 1] % mod)
* (i % mod))
% mod;
}
// dp[N]: Stores the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
// Update dp[i]
dp[i] = ((dp[i - 1] % mod)
* (factorial[i] % mod))
% mod;
}
// Return the answer.
return dp[n];
}
// Driver code
static void Main()
{
int n = 4;
// Function call
Console.WriteLine(ValOfTheExpression(n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to implement
// the above approach
let mod = 1000000007;
// Function to find the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
function ValOfTheExpression(n)
{
// factorial[i]: Stores factorial of i
let factorial = new Array(n + 1);
// Base Case for factorial
factorial[0] = factorial[1] = 1;
// Precompute the factorial
for (let i = 2; i <= n; i++)
{
factorial[i] = ((factorial[i - 1] % mod) *
(i % mod)) % mod;
}
// dp[N]: Stores the value of the expression
// ( N^1 * (N – 1)^2 * … * 1^N) % (109 + 7).
let dp = new Array(n + 1);
dp[1] = 1;
for (let i = 2; i <= n; i++)
{
// Update dp[i]
dp[i] = ((dp[i - 1] % mod) *
(factorial[i] % mod)) % mod;
}
// Return the answer.
return dp[n];
}
let n = 4;
// Function call
document.write(ValOfTheExpression(n));
</script>
Producción:
288
Complejidad de Tiempo: O(N )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pavang2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA