階乘尾零Leetcode解決方案


難度級別 容易獎學金
經常問 彭博社
數學

問題陳述

在這個問題中,我們必須找出n中會有多少尾隨零!
給定n作為輸入。

就像五分之一的尾隨零!
五! = 5 * 5 * 4 * 3 * 2 = 1

n = 3
0

說明:3! = 6,無尾隨零

n = 0
0

說明:0! = 1,無尾隨零

 

在n中查找尾隨零的數目! ,一個簡單的方法是計算n! 並檢查最後有多少個零。 我們可以簡單地執行以下操作:檢查是否將數字除以10,我們得到餘數0,然後通過將最後的零除以10,我們將其計數,直到每次得到的餘數等於零。

但是這種方法對於簡單的整數不可行,因為我們知道n! 是一個很大的數字。 在C ++和Java中,簡單的整數大小最多為64位,最多只能存儲2 ^ 63 – 1的整數。這近似於10 ^ 18。 在Java中,我們可以使用BigInteger類來存儲像n!這樣的大數字。 但是這種暴力方法具有很大的時間和空間複雜性。

在這裡,我們將討論在n中尋找尾隨零的有效解決方案!

方法1(計數因子5)

我們可以說尾隨零的總數等於10是該數字的倍數的計數。 而且我們知道每10個都是由兩個素數2和5的乘積形成的。
因此,如果我們找出數字中有多少個2的因子。 同樣,有多少個5因子。 然後,我們可以說每個元素將結合起來使乘積等於10。因此,尾隨零的總數將等於最小值(計數為2的計數,計數為5的計數)。

現在我們必須在n!中計算這些因素。
n! = 1 * 2 * 3….. *(n-1)* n

因此,我們將迭代從2到n的所有數字(以2遞增,因為它們是至少包含一個2的數字)。
對於每個數字,我們將其重複除以2,直到將其除以2,以找到該數字因式分解中的2的計數。
同樣,要找到該數字中的5,我們將做同樣的事情。
現在,我們將返回這兩個計數中的最小值。

這可行,但我們也可以對其進行一些優化。 我們可以分析一下,我們有從1到n的數字,所以我們總是得到2的冪比5的冪大。
像直到4一樣,我們得到兩個數字,其中2為因數(2和4)。 在5處,我們得到第一個以5為因數的數字。 因此,這將以相似(不斷增加)的計數差異不斷進行。 這是一個可視化圖,它說明了2個因子和5個因子之間的密度如何不同。

階乘尾零Leetcode解決方案

因此,我們可以得出結論:2的計數始終大於n!中的5計數。
因此,我們需要找到僅5的計數,而這將是ans。 這樣,我們將任務減少了一半。

階乘尾零Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    for(int i=5;i<=n;i+=5)
    {
        int x=i;
        while(x>0 && x%5==0)
        {
            ++fives;
            x/=5;
        }
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

Java程序

class Rextester{
    
    public static int trailingZeroes(int n) 
    {
        int fives=0;
        for(int i=5;i<=n;i+=5)
        {
            int x=i;
            while(x>0 && x%5==0)
            {
                ++fives;
                x/=5;
            }
        }
        return fives;
    }
    
  public static void main(String args[])
    {    	
    System.out.println(trailingZeroes(5));
    }
}
1

因子尾隨零Leetcode解的複雜性分析

時間複雜度

上) : 我們正在迭代1到n的所有倍數。 對於每個元素,我們似乎要花費log(n)的時間來查找XNUMX的計數。 但是它攤銷到O(XNUMX),因為我們檢查的絕大多數數字僅包含XNUMX的單個因數。 因此,總時間複雜度保持為O(n)。

空間複雜度 

O(1): 不使用任何額外的內存。

方法2(有效計數因子5)

在上面的方法中,我們看到只需要將5的計數作為給定n!的因子即可。 在上面的方法中,我們遍歷了5的所有倍數,並為每個數字添加了5的計數,並在線性時間內獲得了ans。 我們將做最後的觀察,這將使我們能夠計算對數時間的ans。

客棧! (即從1到n),我們有一些不能被5整除的數字(0為5的計數貢獻5),然後我們有一些可以被25整除的數字(每個貢獻125計數),然後我們有可以被整除的數字XNUMX(這一次來自這些眾多數字的一個額外貢獻),然後被XNUMX(可從這些額外的數字得到的一個額外貢獻)可整除,依此類推。

那麼我們的ans將是所有這些貢獻的總和。
我們可以將所有這些總結如下:
5的總數= n / 5 + n / 25 + n / 125 +…。 很快
直到分母小於n為止,因為在那之後分數的整數值將為零。

步:
用5初始化分母變量。
運行一個 循環,在每次迭代中將n /分母值相加得到結果,並將分母乘以5。運行循環,直到分母<n。

階乘尾零Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

Java程序

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

因子尾隨零Leetcode解的複雜性分析

時間複雜度

O(log(n)): 我們每次將分母乘以5直到小於n。 因此,迭代的總數將為log(n)。

空間複雜度 

O(1): 不使用任何額外的內存。