Factorial program in javascript

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 then pop 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).

Leave a Reply

Your email address will not be published. Required fields are marked *