I'm calculating the trailing zeros of a factorial. My solution is to calculate the factorial then determine how many trailing zeros it has. As you can imagine this isn't very scalable. How can I solve this without calculating the factorial?
I've found these pages on SO: Trailing zeroes in a Factorial Calculating the factorial without trailing zeros efficiently?
However, neither are in Javascript. If you downvote this question please let me know why. Thank-you for your time and feedback.
My solution:
function zeros(n) {
var result = [];
var count = 0;
for (var i = 1; i <= n; i++) {
result.push(i);
} //generating range for factorial function
var factorial = result.reduce(function(acc, el) {
return acc * el;
}, 1); //calculating factorial
factorial = factorial.toString().split('');
for (var j = factorial.length - 1; j > 0; j--) {
if (parseInt(factorial[j]) === 0) {
count += 1;
} else {
break;
}
} //counting trailing zeros
return count;
}
I'm calculating the trailing zeros of a factorial. My solution is to calculate the factorial then determine how many trailing zeros it has. As you can imagine this isn't very scalable. How can I solve this without calculating the factorial?
I've found these pages on SO: Trailing zeroes in a Factorial Calculating the factorial without trailing zeros efficiently?
However, neither are in Javascript. If you downvote this question please let me know why. Thank-you for your time and feedback.
My solution:
function zeros(n) {
var result = [];
var count = 0;
for (var i = 1; i <= n; i++) {
result.push(i);
} //generating range for factorial function
var factorial = result.reduce(function(acc, el) {
return acc * el;
}, 1); //calculating factorial
factorial = factorial.toString().split('');
for (var j = factorial.length - 1; j > 0; j--) {
if (parseInt(factorial[j]) === 0) {
count += 1;
} else {
break;
}
} //counting trailing zeros
return count;
}
Share
Improve this question
asked Nov 18, 2017 at 19:58
BrayheartBrayheart
1673 silver badges17 bronze badges
2
-
Surely it's trivial to convert the C code into JavaScript. In fact here you can just change the first
int
tofunction
and the rest of theint
inside the function intovar
and it runs as JavaScript. – JJJ Commented Nov 18, 2017 at 20:02 - @JJJ I don't know anything about C I didn't know they were that similar. Thankyou! – Brayheart Commented Nov 18, 2017 at 20:06
4 Answers
Reset to default 5Knowing the number of trailing zeroes in a number es down to knowing how many times it can be divided by 10, i.e. by both 5 and 2.
With factorial numbers that is quite easy to count:
f! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16. ... .f
^ ^ ^
The places where a factor 5 gets into the final product are marked. It is clear that factors of 2 occur more often, so the count of factors of 5 are determining the number of trailing zeroes.
Now, when the factor 25 occurs, it should be counted for 2; likewise 125 should count for 3 factors of 5, etc.
You can cover for that with a loop like this:
function zeros(n) {
var result = 0;
while (n = Math.floor(n / 5)) result += n;
return result;
}
public static void main(String[] args) {
int n=23;
String fact= factorial(BigInteger.valueOf(23)).toString();
System.out.format("Factorial value of %d is %s\n", n,fact);
int len=fact.length();
//Check end with zeros
if(fact.matches(".*0*$")){
String[] su=fact.split("0*$");
//Split the pattern from whole string
System.out.println(Arrays.toString(fact.split("0*$")));
//Subtract from the total length
System.out.println("Count of trailing zeros "+(len-su[0].length()));
}
}
public static BigInteger factorial(BigInteger n) {
if (n.equals(BigInteger.ONE) || n.equals(BigInteger.ZERO)) {
return BigInteger.ONE;
}
return n.multiply(factorial(n.subtract(BigInteger.ONE)));
}
You don't really need to calculate the factorial product to count the trailing zeroes.
Here a sample to count the number of trailing zeroes in n!
temp = 5;
zeroes = 0;
//counting the sum of multiples of 5,5^2,5^3....present in n!
while(n>=temp){
fives = n/temp;
zeroes = zeroes + fives;
temp = temp*5;
}
printf("%d",zeroes);
Note that each multiple of 5 in the factorial product will contribute 1 to the number of trailing zeros. On top of this, each multiple of 25 will contribute an additional 1 to the number of trailing zeros. Then, each multiple of 125 will contribute another 1 to the number of trailing zeros, and so on.
Here's a great link to understand the concept behind this: https://brilliant/wiki/trailing-number-of-zeros/
I came across this algorithm somewhere on here can not remember now, but it looks like this,
def zeros(n)
return 0 if n.zero?
k = (Math.log(n)/Math.log(5)).to_i
m = 5**k
n*(m-1)/(4*m)
end
This very effiecient as it does not need a loop.
You can further optimize it to look like this.
def zeros(n)
return 0 if n.zero?
n*(n-1)/(4*n)
end
A javascript translation of this will be.
function zeros(n) {
if (n == 0) return 0;
return n * (n-1)/(4*n);
}
Note that this algorithm is correct till about n >= 1000000000
, in which case the return value has an error margin of +1
, and this error margin increases by +1
every n * 10000
.