JavaScript Program to Count Trailing Zeroes in Factorial of a Number
In this article, we are going to learn how to count trailing zeroes in the factorial of a number in JavaScript. Counting trailing zeroes in the factorial of a number means determining how many consecutive zeros appear at the end of the factorial’s decimal representation. It’s a measure of how many times the factorial value is divisible by 10.
Example:
Input : n = 5
Factorital of 5 i.e. 5! = 5 * 4 * 3 * 2 * 1 = 120
Output : 1
Here we have one trailing 0.
Input : n = 15.
Factorial of 15 i.e. 15! = 15 * 14 * 13 * 12 * 11 ... 3 * 2 * 1 = 1307674368000
Output : 3
Here we have 3 trailing 0.
There are several methods that can be used to Count trailing zeroes in the factorial of a number in JavaScript, which are listed below:
Table of Content
- Approach 1: Using Division method
- Approach 2: Using Recursive division
- Approach 3: Using Logarithms
- Approach 4: Using Prime Factorization
We will explore all the above methods along with their basic implementation with the help of examples.
Approach 1: Using Division method
In this approach we are using repeated division by 5, sum quotients while n >= 5, counting trailing zeroes in factorials.
Syntax:
function trailingZeroes(n) {
let count = 0;
while (n >= 5) {
n = Math.floor(n / 5);
count += n;
}
return count;
};
Example: In this example, we are using a simple division method to find trailing zeroes of 5 and 15, in which 5! = 120 and 15! = 1307674368000.
function trailingZeroes(n) {
let count = 0;
while (n >= 5) {
n = Math.floor(n / 5);
count += n;
}
return count;
}
let num1 = 5;
let num2 = 15;
let result = trailingZeroes(num1);
let result2 = trailingZeroes(num2);
console.log(`Trailing zeroes in ${num1}! = ${result}`);
console.log(`Trailing zeroes in ${num2}! = ${result2}`);
Output
Trailing zeroes in 5! = 1 Trailing zeroes in 15! = 3
Approach 2: Using Recursive division
In this approach, we Recursively divide the number by 5, adding quotients. Repeat until the number becomes 0. The sum of quotients gives trailing zeroes in factorial.
Syntax:
function trailingZeroes(n) {
if (n === 0) return 0;
return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));
};
Example: In this example, we are using the recursive method to find trailing zeroes of 15.
function trailingZeroes(n) {
if (n === 0) return 0;
return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));
}
let num = 15;
let result = trailingZeroes(num);
console.log(`Trailing zeroes in ${num}! = ${result}`);
Output
Trailing zeroes in 15! = 3
Approach 3: Using Logarithms
In this approach, we are Counting trailing zeroes by iteratively dividing the number by powers of 5. Accumulate quotients for total trailing zeroes in the factorial.
Syntax:
function trailingZeroes(n) {
let count = 0;
for (let i = 5; n / i >= 1; i *= 5) {
count += Math.floor(n / i);
}
return count;
};
Example: In this example, we are using Logarithms to find trailing zeroes of 25, in which 25! = 15511210043330985984000000. so here are 6 trailing zeroes.
function trailingZeroes(n) {
let count = 0;
for (let i = 5; n / i >= 1; i *= 5) {
count += Math.floor(n / i);
}
return count;
}
const num = 25;
const result = trailingZeroes(num);
console.log(`Trailing zeroes in ${num}! = ${result}`);
Output
Trailing zeroes in 25! = 6
Approach 4: Using Prime Factorization
In this approach, we find the prime factorization of the given number, n. Since trailing zeroes in a factorial result from pairs of 2s and 5s, and 2s occur more frequently than 5s in the prime factorization of integers, we count the occurrences of 5s to determine the number of trailing zeroes.
Syntax:
function trailingZeroes(n) {
let count = 0;
for (let i = 5; n / i >= 1; i *= 5) {
count += Math.floor(n / i);
}
return count;
};
Example: In this example, we will use prime factorization to find trailing zeroes of 30.
function trailingZeroes(n) {
let count = 0;
for (let i = 5; n / i >= 1; i *= 5) {
count += Math.floor(n / i);
}
return count;
}
const num = 30;
const result = trailingZeroes(num);
console.log(`Trailing zeroes in ${num}! = ${result}`);
Output
Trailing zeroes in 30! = 7