Given a non-negative integer N, find its factorial.
The factorial of N is written as N! and means:
N! = N * (N - 1) * (N - 2) * ... * 2 * 1
For N = 0, the factorial is defined as 1.
Example 1
Input: n = 5
Output: 120
Explanation: 5! = 5 * 4 * 3 * 2 * 1 = 120
Example 2
Input: n = 0
Output: 1
Explanation: By definition, 0! = 1.
Approach
For example, to find 5!, the factorial goes like this: 1 * 2 * 3 * 4 * 5
That immediately suggests keeping one answer variable and growing it step by step. Start with 1, and then multiply it by every number from 2 to N.
The small but important edge case is N = 0. Since no numbers need to be multiplied, the result stays 1.
Algorithm
Start with a variable
factas1, because factorial is built through multiplication and1is the correct starting value.Check every number from
2toN, because each of those values must be included in the product.Multiply
factby the current number in every step so the answer keeps growing towardN!.When the loop finishes, return
fact, because it now stores the product of all numbers from1toN.
Key Points
0! = 1, so whenNis0, the answer is1.Factorial is usually defined only for non-negative integers.
Factorial values grow very fast, so large inputs may overflow normal integer types in some languages.
Dry Run
Factorial of a Number Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the factorial of n using iterative multiplication. */ long long factorial(int n) { // Stores the running factorial value long long fact = 1; // Start from 2 because multiplying by 1 does not matter. for (int i = 2; i <= n; i++) { // Multiply current number into running factorial value. fact *= i; } return fact; }};// Driver code startsint main() { int n = 5; Solution obj; cout << obj.factorial(n) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because the loop runs from 2 to N.
Space Complexity: O(1), because only one main answer variable is used.
Interview follow-up Questions
The multiplication answer needs a starting value that does not change the result. Multiplying by 1 keeps the product correct.
Be the first to add a comment.