66 lines
1.2 KiB
C++
66 lines
1.2 KiB
C++
// 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);
|
|
}
|
|
}
|