Factorial

• Factorial of a positive integer n, denoted by n! is the product of all positive integers <= n

Find factorial of a given number, where n>=0

Ip: n = 4
Op: 24, 
Ip: n= 6
Op:720
Ip: n=0
Op: 1

Iterative solution:

1int fact(int n){
2    int res = 1;
3    for(int i = 2; i<=n;i++){
4        res=res*i;
5    }
6    return res;
7} //TC: O(n), SC: O(1)

Recursive solution:

1int fact(int n){
2    if(n==0 || n==1) return 1;
3    return n * fact(n-1);
4} // TC: O(n), SC:O(n)

Find trailing zeroes in a factorial.

Input: n = 5
Output: 1 
Factorial of 5 is 120 which has one trailing 0.

Input: n = 20
Output: 4
Factorial of 20 is 2432902008176640000 which has
4 trailing zeroes.

Input: n = 100
Output: 24

Naive solution:

 1const fact = (n) => {
 2    if(n===0||n===1) return 1;
 3    let fact = 1;
 4    for(let i = 2; i <= n; i++){
 5        fact *=i;
 6    }
 7    return fact;
 8}
 9const trailingZeroes = (n) =>{
10   let res = fact(n);
11   let count = 0;
12   while(res%10===0){
13       count++;
14       res/=10;
15   }
16   return count;
17}
18console.log(trailingZeroes(5)); // 2
19//TC: O(n);

Major issue with the above solution is it causes overflow even if the n is slightly higher.

Efficient solution:

Count number of 2s and 5s in the prime factorization of given factorial.

• One interesting fact about factorials is number of 5s are < number of 2s. So we simply need to find number of 5s in the given number.
• 1x2x3x4x5x6x7x8x9x10….n -> Notice that every 5th number is going to have 5 as a prime factor. If we have a n as a number, then we have atleast floor(n/5) prime factors.
  • Why atleast? consider the case of 25. We have two 5s as prime factors. We have to consider these as well.

  • General formula: Trailing zero count = floor(n/5) + floor(n/25) + floor(n/125) + ……

 1const efficientTrailZeroes = (n) =>{
 2    let res = 0;
 3    //first ompute n/5, then compute n/25, then compute n /125 ...
 4    for(let i = 5; i <=n; i *=5){
 5        res += n/i;
 6    }
 7    return Math.floor(res);
 8}
 9console.log(efficientTrailZeroes(251));
10// 5^k <=n , k <= log5(n); TC: O(log5(n)) 

This solution solves the major issue of overflow because we are not calculating factorial here , we are dividing the given number based on number of 5s