Factorial of a Number
The factorial of a non-negative integer n is a mathematical function denoted by n! It represents the product of all positive integers from 1 up to n.
Examples :
Input: 5
Output: 120
Explanation: 5! is equal to 5*4*3*2*1 = 120.
Input: 4
Output: 24
Explanation: 4! is equal to 4*3*2*1 = 24.
The basic definition of factorial is: n! = n * (n-1) * (n-2) * (n-3) * ….. * 1.
By definition 0! is equal to 1.
To compute the factorial of a number n, start by initializing a variable result to 1. Then, use a loop that iterates from 1 to n, multiplying the result by each loop counter in each iteration. After completing the loop, the result will contain the factorial of n i.e. n!
Code Implementation
C++ Code Try on Compiler!
// Function to calculate factorial using an iterative approach
long long factorial(int n) {
// Initialize result as 1 (since factorial of 0 is 1)
long long result = 1;
// Loop from 1 to n and multiply each number with result
for (int i = 2; i <= n; i++) {
result *= i;
}
// Return the calculated factorial
return result;
}Java Code Try on Compiler!
public class Factorial {
// Function to calculate factorial using an iterative approach
public static long factorial(int n) {
long result = 1; // Initialize result as 1
for (int i = 2; i <= n; i++) {
result *= i; // Multiply each number with result
}
return result; // Return the calculated factorial
}
}Python Code Try on Compiler!
# Function to calculate factorial using an iterative approach
def factorial(n):
result = 1 # Initialize result as 1
for i in range(2, n + 1): # Loop from 2 to n
result *= i # Multiply each number with result
return result # Return the calculated factorialJavascript Code Try on Compiler!
function factorial(n) {
let result = 1; // Initialize result as 1
for (let i = 2; i <= n; i++) { // Loop from 2 to n
result *= i; // Multiply each number with result
}
return result; // Return the calculated factorial
}Time Complexity : O(n)
The time complexity of computing the factorial of n is O(n). This is because the algorithm involves a single loop that iterates from 1 to n. A constant-time operation (multiplication and assignment) is performed in each iteration. Thus, the total time complexity is proportional to the number of iterations, n.
Space Complexity : O(n)
The space complexity of this algorithm is O(1). The algorithm uses a fixed amount of extra space regardless of the input size. It only requires a few variables (like the result and the loop counter), and the amount of memory needed does not grow with n.