Фацториал Траилинг Зероес Леетцоде решење


Ниво тешкоће Лако
Често питани у Блоомберг
Математика

Изјава о проблему

У овом проблему морамо да сазнамо колико ће нула бити у н!
Дати н као улаз.

Као да постоји једна пратећа нула у 5!
5! = 5 * 4 * 3 * 2 * 1 = 120

Пример

n = 3
0

Објашњење: 3! = 6, без пратеће нуле

n = 0
0

Објашњење: 0! = 1, без пратеће нуле

 

Да бисте пронашли број пратећих нула у н! , једноставан начин је израчунавање н! и проверите колико нула има на крају. То можемо учинити једноставним проверавањем да ли дељењем броја са 10 добијемо остатак 0, а затим уклонимо последњу нулу тако што га делимо са 10. То можемо рачунати док сваки пут не добијемо остатак једнак нули.

Али овај приступ није практичан са једноставним целим бројевима, јер знамо н! је веома велик број. У Ц ++ и Јави једноставна целобројна величина је у најбољем случају 64-битна која може да сачува цели број само до ограничења од 2 ^ 63 - 1. Што је приближно 10 ^ 18. У јави можемо да користимо класу БигИнтегер за складиштење великих бројева попут н !. Али овај груби приступ има велику временску и просторну сложеност.

Овде ћемо разговарати о ефикасном решењу за проналажење пратећих нула у н!

Приступ 1 (Фактори бројања 5)

Можемо рећи да ће укупан број пратећих нула бити једнак бројању колико је пута 10 фактор тог броја. И знамо да је сваких 10 формирано од производа два проста броја 2 и 5.
Па ако откријемо колико фактора броја 2 има у броју. Слично томе колико има фактора петица. Тада можемо рећи да ће се сваки од ових комбиновати да би производ био једнак 5. Стога ће укупан број пратећих нула бити једнак минимуму (бројање 10, бројање 2).

Сада ове факторе морамо рачунати у н !.
н! = 1 * 2 * 3… .. * (н-1) * н

Дакле, извршићемо итерацију преко свих бројева од 2 до н (увећавајући за 2, јер су то бројеви који садрже најмање једна два).
За сваки број ћемо га више пута поделити са 2 док не буде дељив са 2 да бисмо пронашли број 2 у факторизацији тог броја.
Слично томе, да бисмо пронашли број 5 у том броју, урадићемо исту ствар.
Сада ћемо вратити минимум из ове две тачке.

Ово ради, али можемо и мало да га оптимизујемо. Можемо анализирати да имамо бројеве од 1 до н, па бисмо увек добили овлашћења 2 више од овлашћења 5.
Као до 4, добијамо два броја која као фактор имају 2 (2 и 4). Са 5 добијамо први број који има фактор 5. Дакле, ово ће се наставити и даље са сличном (све већом) разликом бројања. Ево визуелизације која илуструје како се разликује густина између 2 и 5 фактора.

Фацториал Траилинг Зероес Леетцоде решење

Стога можемо закључити да је број 2 увек већи од броја 5 у н !.
Дакле, треба да нађемо бројање само пет и то ће бити анс. На овај начин смањујемо задатак за пола.

Имплементација решења факторских пратећих нула Леетцоде

Програм Ц ++

#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

Јава Програм

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

Анализа сложености решења факторских пратећих нула Леетцоде

Сложеност времена

На) : понављамо преко свих вишекратника од пет до н. Могло би изгледати као да за сваки елемент који користимо лог (н) време пронађемо број петица. Али амортизује се на О (1), јер велика већина бројева које смо проверили садржи само један фактор пет. Отуда укупна временска сложеност остаје као О (н).

Сложеност простора 

О (1): Не користи се додатна меморија.

Приступ 2 (бројање фактора од 5 ефикасно)

У горњем приступу видели смо да бројање 5 треба да нађемо само као фактор датог н !. У горњем приступу смо прегледали све вишекратнике 5 и додали број 5 за сваки број и добили своје одговоре у линеарном времену. Направићемо једно коначно запажање које ће нам омогућити да израчунамо анс у логаритамском времену.

Гостионица! (тј. од 1 до н) имамо неке бројеве који нису дељиви са 5 (доприносећи 0 за бројање 5), затим имамо неке бројеве који су дељиви са 5 (сваки доприноси једном броју), затим имамо бројеве који су дељиви са 25 (овај пут један додатни прилог од ових многобројних бројева), затим дељив са 125 (један додатни прилог од ових), попут овог и тако даље.

Тада ће наш анс бити збир свих ових доприноса.
Све ово можемо сумирати на следећи начин:
укупан број 5 = н / 5 + н / 25 + н / 125 +…. ускоро
То ће ићи док називник не буде мањи од н, јер ће након тога интегрална вредност разломка бити нула.

korak:
Иницијализовати променљиву називника са 5.
Покрени петља, у сваку итерацију додајте вредност н / називника да бисте добили и помножите називник са 5. Покрените петљу до називника <н.

Имплементација решења факторских пратећих нула Леетцоде

Програм Ц ++

#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

Јава Програм

#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

Анализа сложености решења факторских пратећих нула Леетцоде

Сложеност времена

О (лог (н)): множимо именитељ са 5 сваки пут док не буде мање од н. Отуда ће укупан број итерација бити лог (н).

Сложеност простора 

О (1): Не користи се додатна меморија.