首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

LeetCode 172:階乘尾部零的個數(對數時間解法)

     編輯:關於C++

題目描述

給定整數 n,返回 n! 末尾 0 的個數。要求對數時間複雜度。

數學洞察

尾部 0 由因子 10 產生,即 2 和 5 配對。階乘中因子 2 遠多於 5,所以 0 的個數等於因子 5 的個數。每 5 個數貢獻一個 5,每 25 個額外貢獻一個,以此類推。公式:n/5 + n/25 + n/125 + ...

代碼實現 (C++)

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

複雜度

  • 時間:O(log_5 n)
  • 空間:O(1)
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved