Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummath-number-theory

Factorial Trailing Zeroes

Problem (restated)

Given an integer n, return how many trailing zeros n! has. Do not compute the factorial.

Intuition

A trailing zero is a factor of 10 = 2 × 5. There are always more 2s than 5s in n!, so the count of 5s is the answer. Multiples of 25 contribute an extra 5, 125 another, and so on: ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ….

Approaches

Count factors of 5

Unverified

Time O(log n)Space O(1)

Idea. Repeatedly n = ⌊n/5⌋ and add n into the total until n is 0.

Walkthrough. n = 25 → 5 + 1 = 6. n = 3 → 0. n = 10 → 2.

Trade-offs. Computing n! overflows immediately. This is O(log₅ n) additions. Do not forget the extra 5s from 25, 125, …

Solution

export function trailingZeroes(n: number): number {
  let z = 0;
  while (n > 0) {
    n = Math.floor(n / 5);
    z += n;
  }
  return z;
}

export function trailingZeroes(n: number): number {
  let z = 0;
  while (n > 0) {
    n = Math.floor(n / 5);
    z += n;
  }
  return z;
}

Template connection

Factorials / divisibility shape of Math & Number Theory: count prime factors instead of expanding the product.

Reflection

A trailing zero is a factor of 10. There are more factors of 2 than of 5, so count the 5s: n/5 + n/25 + n/125.
25 contributes two 5s and 125 contributes three. The loop adds that by repeatedly dividing n by 5.
n < 5 answers 0. 25 answers 6. Writing n! overflows.