LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 实现大数阶乘，直接统计末尾 0 的数目，但这种做法会超时

class Solution {
 public:
  int trailingZeroes(int n) {
    vector<char> v{1};
    for (int i = 1; i <= n; ++i) {  // 依次计算 i 的阶乘
      int carry = 0;                // 进位值
      for (auto& x : v) {           // 依次计算结果的各个数位
        int t = x * i + carry;
        x = t % 10;
        carry = t / 10;  // 其他用于进位
      }
      while (carry) {  // 如果还有多余的进位值依次置于高位
        v.emplace_back(carry % 10);  // 放置高位值
        carry /= 10;
      }
    }
    return find_if(begin(v), end(v), [](auto& x) { return x; }) - begin(v);
  }
};

• 计算末尾 0 的数量，实际就是计算因数中 2 和 5 的数量中较小的那个。但因数 5 的数目肯定比 2 少，因此只要计算包含 5 的因数个数即可

10! 2
15! 3
20! 4
25! 6 = 5 + 1（25 额外提供 1 个 5）
30! 7
50! 12 = 10 + 2（25 和 50 都额外提供 1 个 5）
120! 28 = 24 + 4（25、50、75、100 额外提供 1 个 5）
125! 31 = 25 + 5 + 1（125 在额外提供 1 个 5 之后，还要额外提供一个 5）

因此结果为 n / 5 + n / 25 + n / 125 + ...

• 实现如下

class Solution {
 public:
  int trailingZeroes(int n) {
    int res = 0;
    while (n) {
      n /= 5;
      res += n;
    }
    return res;
  }
};