// Calculate the number of trailing zeros on n!

#define CATCH_CONFIG_MAIN
#include <catch.hpp>

#include <cstdint>

using Number = uint64_t;

static Number factorial(int n) {
  switch (n) {
    case 1:
      return 1;
    case 2:
      return 2;
    default:
      return n * factorial(n-1);
  }
}

static int zeros(int n) {
  if (n < 5) {
    return 0;
  }

  // Count the factors that will add a zero.
  if (n % 5 == 0) {
    return 1 + zeros(n-1);
  }
  return 0 + zeros(n-1);
}

TEST_CASE("cc19.3", "zeros") {
  static const struct {
    int n;
    Number fact;
    int zeros;
  } tests[] = {
    { 1, 1, 0 },
    { 2, 2, 0 },
    { 3, 6, 0 },
    { 4, 24, 0 },
    { 5, 120, 1 },
    { 6, 720, 1 },
    { 7, 5040, 1 },
    { 8, 40320, 1 },
    { 9, 362880, 1 },
    { 10, 3628800, 2 },
    { 11, 39916800, 2 },
    { 12, 479001600, 2 },
    { 13, 6227020800, 2 },
    { 14, 87178291200, 2 },
    { 15, 1307674368000, 3 },
    { 16, 20922789888000, 3 },
    { 17, 355687428096000, 3 },
    { 18, 6402373705728000, 3 },
    { 19, 121645100408832000, 3 },
    { 20, 2432902008176640000, 4 },
  };

  for (const auto& test : tests) {
    CHECK(factorial(test.n) == test.fact);
    CHECK(zeros(test.n) == test.zeros);
  }
}