factorial_trailing_zeros.scala

import scala.annotation.tailrec
// v0 - simple but slow

def factorial(n: Int): BigInt =
  (1 to n).foldLeft(BigInt(1))((a, b) => a * b)

def numberTrailingZeros(str: String): Int =
  str.split("[1-9]").last.length

def numberTrailingZerosOfFactorial0(n: Int): Int =
  numberTrailingZeros(factorial(n).toString)

// v1 - fast, elegant, the right solution in most cases

def timesFiveDivides(n: BigInt): BigInt =
  if (n % 5 == 0 )
    1 + timesFiveDivides(n/5)
  else
    0

def numberTrailingZerosOfFactorial01(n: Int): BigInt =
  timesFiveDivides(factorial(n))

def timesFiveDividesFactorial(n: Int): BigInt =
  (1 to n).map(i => timesFiveDivides(i)).sum

val numberTrailingZerosOfFactorial10: Function[Int, BigInt] = timesFiveDividesFactorial

def betterTimesFiveDividesFactorial(n: BigInt): BigInt =
  val next = n / 5
  if (next == 0)
    0
  else
    next + betterTimesFiveDividesFactorial(next)

val numberTrailingZerosOfFactorial11: Function[BigInt, BigInt] = betterTimesFiveDividesFactorial

// v2 - fast but very confusing.

case class Power5(index: Int, power: BigInt, sum: BigInt) {
  def next: Power5 = Power5(index + 1, power * 5, power + sum)
}

object PowersOfFive {
  var cache = collection.mutable.Map[Int, Power5](0 -> Power5(0, BigInt(1), BigInt(0)))
  var highestPower: Int = 0
  def get(n: Int): Power5 =
    if (n <= highestPower)
      cache(n)
    else
      cacheMore(cache(highestPower), n)

  @tailrec
  def cacheMore(pow: Power5, n: Int): Power5 =
    if (pow.index == n)
      pow
    else
      val newPow = pow.next
      cache(newPow.index) = newPow
      highestPower += 1
      cacheMore(newPow, n)
}

val log5 = math.log(5)

def logBase5(n: BigInt): Int =
  math.ceil(math.log(n.toFloat)/log5).toInt

def ctfdf(n: BigInt, pow: Power5): BigInt =
  pow match {
    case Power5(i, power, sum) =>
      if (n < 5)
        0
      else if (power > n)
        ctfdf(n, PowersOfFive.get(i-1))
      else
        sum + ctfdf(n - power, pow)
  }

def cachedTimesFiveDividesFactorial(n: BigInt): BigInt =
  ctfdf(n, PowersOfFive.get(logBase5(n)))

val numberTrailingZerosOfFactorial2: Function[BigInt, BigInt] = cachedTimesFiveDividesFactorial

// v3 - interesting but inefficient

def approxTimesFiveDividesFactorial(n: BigInt): BigInt =
  (n-1)/4

def base5digitsSum(n: BigInt): BigInt =
  if (n == 0)
    0
  else
    base5digitsSum(n/5) + (n % 5)

def error(n: BigInt): BigInt =
  (base5digitsSum(n) - 1)/4

def sillyTimesFiveDividesFactorial(n: BigInt): BigInt =
  approxTimesFiveDividesFactorial(n) - error(n)

val numberTrailingZerosOfFactorial3: Function[BigInt, BigInt] = sillyTimesFiveDividesFactorial