We will implement three different program to find the factorial of a given number in Javascript. Everything will be written in ES6.
- Using brute force method.
- With recursion.
- Using Stack.
Factorial: Product of all the numbers from 1 to the given number.
Example
Input: 5 10 12 Output: 120 3628800 479001600
Factorial with Brute Force Method.
Implementation
- We will loop till the given number is greater than 0.
- With each iteration we will reduce the number and multiply it with the previous number and store it.
let factorial = (num) => { let product = 1; //loop until num is greater than 0 while(num > 0){ //multiply and store the output product *= num; num--; } return product; }
Input: console.log(factorial(5)); console.log(factorial(10)); console.log(factorial(12)); Output: 120 3628800 479001600
Time complexity: O(n).
Space complexity: O(1).
Time and Space complexity
- We will be looping till the number is greater than 0, so Time complexity is O(n).
- We are using constant space, so Space complexity is O(1).
Using recursion to find the factorial
Implementation
- We will create a function and check if given number is less than 0 then return 1.
- Else we will call the same function with the same number reduced by 1.
let recursiveFactorial = (num) => { //if num is less than 1 then return 1; if(num < 1){ return 1; } //return product of num and one number less than num return num * recursiveFactorial(num - 1); }
OR
let recursiveFactorial = (num) => { return num < 1 ? 1 : num * recursiveFactorial(num - 1); }
Input: console.log(recursiveFactorial(5)); console.log(recursiveFactorial(10)); console.log(recursiveFactorial(12)); Output: 120 3628800 479001600 /*How it works recursiveFactorial(5) ^ return 5 * recursiveFactorial(4) | | recursiveFactorial(4) | return 4 * recursiveFactorial(3) | | recursiveFactorial(3) | return 3 * recursiveFactorial(2) | | recursiveFactorial(2) | return 2 * recursiveFactorial(1) | | recursiveFactorial(1) | return 1 * recursiveFactorial(0) | | recursiveFactorial(0) | if(0 < 1){ | return 1; | } | 1 * 1 * 2 * 3 * 4 * 5 = 120 */
Time complexity: O(n).
Space complexity: O(n).
Time and Space complexity
- We are calling the same function until the num is greater than 0, so Time complexity is O(n).
- Each function is stored in stack in recursive function, so Space complexity is O(n).
Using Stack
Implementation
- We will
push
each number from 1 to the given number in Stack. - And then
pop
each number from Stack and multiply it to find the factorial.
let factorialWithStack = (num) => { let s = new Stack(); while(num > 0){ //num-- first pushes the num then decrements it s.push(num--); } let product = 1; while(!s.isEmpty()){ //multiply each item product *= s.pop(); } return product; }
Input: console.log(factorialWithStack(5)); console.log(factorialWithStack(10)); console.log(factorialWithStack(12)); Output: 120 3628800 479001600
Time complexity: O(n).
Space complexity: O(n).
Time and Space complexity
- We are
pushing
each number from 1 to the given number in Stack which will take O(n) and thenpop
each number and multiply it in O(n), As both of these are running one after another, Time complexity is O(n + n) = O(n). - We are storing each number from 1 to the given number, so Space complexity is O(n).