Решение за факторски заостанувања на нулите Leetcode  


Ниво на тешкотија Лесно
Често прашувано во Блумберг
алгоритми кодирање интервју интервју подготви LeetCode LeetCodeSolutions Математика

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

Во овој проблем треба да откриеме колку заостанувачки нули ќе има во n!
Со оглед на n како влез.

Како да има една заостанувачка нула во 5!
5! = 5 * 4 * 3 * 2 * 1 = 120

пример

n = 3

Објаснување: 3! = 6, без заостанувачка нула

n = 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 !.
н! = 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 фактори.

Видете исто така
Решение за лек-код на Паскал Триаголник II

Решение за факторски заостанувања на нулите LeetcodeПин

Затоа можеме да заклучиме дека бројот на 2 е секогаш поголем од бројот на 5 во n !.
Значи, треба да го најдеме само броењето на 5 и тоа ќе бидат антите. На овој начин ја намалуваме задачата за половина.

Имплементација на решението за лек-код на факторите што заостануваат во нули

Програма 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

Анализа на комплексноста на решението за лек-код со фактори што заостануваат во нули

Временска комплексност

На) : повторуваме над сите множители од пет до н. Можеби изгледа како за секој елемент што го земаме во дневник (n) време за да најдеме броење на петки. Но, тоа се амортизира на О (1) затоа што огромното мнозинство на броеви што ги проверивме содржи само единечен фактор пет. Оттука, вкупната временска сложеност останува како O (n).

Комплексноста на просторот 

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

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

Во горенаведениот пристап видовме дека треба да го најдеме броењето на 5-те само како фактор на дадениот n !. Во горенаведениот пристап, ние ги обележавме сите множители од 5 и додадеме броење на 5 за секој број и ги добивме нашите ансамбли во линеарно време. Willе направиме едно последно набудување што ќе ни овозможи да ги пресметаме ансите во логаритамско време.

Во н! (т.е. од 1 до n) имаме некои броеви кои не се делат со 5 (придонесувајќи 0 за броење на 5), тогаш имаме некои броеви што се делат со 5 (секој придонесува по едно броење), тогаш имаме броеви што се делат со 25 (овој пат еден дополнителен придонес од овие бројки), потоа може да се подели со 125 (еден дополнителен придонес од овие), вака и така натаму.

Видете исто така
Обратни самогласки на решетка за низа код

Тогаш нашите анс ќе бидат збир на сите овие придонеси.
Сите овие можеме да ги сумираме подолу:
вкупно броење на 5-те = n / 5 + n / 25 + n / 125 +. така натаму
Ова ќе оди додека именителот е помал од n затоа што после тоа интегралната вредност на дропката ќе биде нула.

Чекор:
Иницијализирај ја променливата на именителот со 5.
Стартувај јамка, во секоја повторување додадете n / именител за да резултира и множете го именителот со 5. Извршете ја јамката до именителот <n.

Имплементација на решението за лек-код на факторите што заостануваат во нули

Програма 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

Анализа на комплексноста на решението за лек-код со фактори што заостануваат во нули

Временска комплексност

О (дневник (н)): ние размножуваме именител со 5 секој пат додека не биде помал од n. Оттука, вкупниот број на повторувања ќе биде дневник (n).

Комплексноста на просторот 

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

1