C++ Program to Find Factorial of a Number Using Dynamic Programming
The Factorial of a number N can be defined as the product of numbers from 1 to the number N. More formally factorial of n can be defined by function,
[Tex]f(n) = 1 \times 2 \times 3 \times… \ n[/Tex]
In this article, we will learn how to find the factorial of a number using dynamic programming in C++.
Example:
Input: n = 5 Output: Factorial = 120
Factorial of a Number Using Dynamic Programming in C++
To find the factorial of the number N using dynamic programming, we will first define an array of size (N + 1) and then define dp[0]=1 and dp[1]=1 . After that, we will fill the dp array by multiplying the current index by the value in dp array at previous index.
Approach
- Define an array named as dp.
- Declare dp[0]=1 abd dp[1]=1.
- Start a loop from 1 to N.
- In each iteration of the loop, do dp[i]=i*dp[i-1].
- The value at dp[N] will correspond to the factorial of number N.
C++ Program to Find the Factorial of a Number Using Dynamic Programming
C++
// CPP Program to illustrate how to Find the Factorial of a // Number Using Dynamic Programming #include <iostream> #include <vector> using namespace std; int main() { // Number to find the factorial of int num = 5; // Vector to store factorials vector< long long > factorial(num + 1); // Base case factorial[0] = 1; // Calculate factorials for ( int i = 1; i <= num; i++) { factorial[i] = i * factorial[i - 1]; } // Print the factorial of the number cout << "Factorial of " << num << " is: " << factorial[num] << endl; return 0; } |
Output
Factorial of 5 is: 120
Time complexity: O(N)
Space complexity: O(N)
This method is efficient for large numbers or when the factorial function is called multiple times.