Problem Statement: Given a number X, print its factorial.
To obtain the factorial of a number, it has to be multiplied by all the whole numbers preceding it. More precisely X! = X*(X-1)*(X-2) … 1.
Note: X is always a positive number.
Examples:
Example 1: Input: X = 5 Output: 120 Explanation: 5! = 5*4*3*2*1 Example 2: Input: X = 3 Output: 6 Explanation: 3!=3*2*1
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Iterative
Approach:
Since the factorial of X will be the product of the number itself and all its preceding numbers we can run loop i, from 1 to X. In every iteration current i, is multiplied with the product so far.
Code:
C++ Code
#include <iostream>
using namespace std;
int factorial(int X) {
int ans = 1;
for (int i = 1; i <= X; i++) {
ans = ans * i;
}
return ans;
}
int main() {
int X = 5;
int result = factorial(X);
cout << "The factorial of " << X << " is " << result;
}
Output: The factorial of 5 is 120
Time Complexity: O(n)
Space Complexity: O(1)
Java Code
public class Main {
static int factorial(int X) {
int ans = 1;
for (int i = 1; i <= X; i++) {
ans = ans * i;
}
return ans;
}
public static void main(String[] args) {
int X = 5;
int result = factorial(X);
System.out.println("The factorial of " + X + " is " + result);
}
}
Output: The factorial of 5 is 120
Time Complexity: O(n)
Space Complexity: O(1)
Solution 2: Recursive
Approach: To apply recursion we have to decompose the larger problem into a smaller problem. In the process of decomposition, the smaller problem should eventually lead to the base case.
Factorial of X can also be written as X*(X-1)!
Again (X-1)! = (X-1)*(X-2)!
Therefore a smaller instance of the same problem contributes to the original larger problem.
Now that we have understood the basic thought process let’s understand how to solve it:-
- Make a function to compute factorial that accepts an integer as parameter.
- Continue to recursively call (X-1)!
- Stop when X = 0. Factorial of 0 is 1.Since we already know the answer to this sub problem this will be our base case.
Code:
C++ Code
#include <iostream>
using namespace std;
int factorial(int X) {
if (X == 0) {
return 1;
}
return X * factorial(X - 1);
}
int main() {
int X = 5;
int result = factorial(X);
cout << "The factorial of " << X << " is " << result;
}
Output: The factorial of 5 is 120
Time Complexity: O(n)
Space Complexity: O(1)
Java Coding
public class Main {
static int factorial(int X) {
if (X == 0) {
return 1;
}
return X * factorial(X - 1);
}
public static void main(String[] args) {
int X = 5;
int result = factorial(X);
System.out.println("The factorial of " + X + " is " + result);
}
}
Output: The factorial of 5 is 120
Time Complexity: O(n)
Space Complexity: O(1)
Special thanks to Somparna Chakrabarti for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article