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;
}

• javascript

• Surely it's trivial to convert the C code into JavaScript. In fact here you can just change the first int to function and the rest of the int inside the function into var 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 4

Knowing 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.