程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Factorial Trailing Zeroes

leetcode筆記:Factorial Trailing Zeroes

編輯:C++入門知識

leetcode筆記:Factorial Trailing Zeroes


一.題目描述

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

二.題目分析

題目的要求是,給定一個整數n,找出n!結果的末尾為0的數的個數。暴力法是首先求出n!,然後直接計算末尾0的個數。(重復(n!)/10,直到余數非0為止),若輸入的n 值過大時,在計算階乘時會導致溢出,因此該方法並不好用。

http://www.cnblogs.com/ganganloveu/p/4193373.html 給出一種很巧妙的解決方法:

事實上,只要對n的階乘n!,做因數分解:n!=2^x*3^y*5^z*...

顯然0的個數等於min(x,z),並且經證明,可以得到:min(x,z)==z

例如:

n = 5時,5!的質因數分解:5! = 2 * 2 * 2 * 3 * 5 中包含321312。後綴0的個數是1

n = 11時,11!的質因數分解:11! = 2^8 * 3^4 * 5^2 * 7 中包含824325。後綴0的個數是2

證明:

對於階乘而言,也就是1*2*3*...*n,設[n/k]代表1~n中能被k整除的個數
顯然有,[n/2] > [n/5] (左邊是逢21,右邊是逢51)
[n/2^2] > [n/5^2](左邊是逢41,右邊是逢251)
……
[n/2^p] > [n/5^p](左邊是逢2^p1,右邊是逢5^p1)
隨著冪次p的上升,出現2^p的概率會遠大於出現5^p的概率。
因此左邊的加和一定大於右邊的加和,也就是n!質因數分解中,2的次冪一定大於5的次冪。

三.示例代碼

#include 
using namespace std;

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

四.小結

這道題的代碼很少,但是要從題目中把復雜的要求轉化為簡單的運算是需要推導的,總體來說還是需要費一定的功夫。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved