Factorial Trailing Zeroes Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган Bloomberg
Math

Маселени билдирүү

Бул көйгөйдөн кийин, nде акыркы нөлдөр канча болорун билишибиз керек!
Киргизүү катары n берилген.

5те бир акыркы нөл бар сыяктуу!
5! = 5 * 4 * 3 * 2 * 1 = 120

мисал

n = 3
0

Түшүндүрмө: 3! = 6, нөл жок

n = 0
0

Түшүндүрмө: 0! = 1, нөл жок

 

Ндеги акыркы нөлдөрдүн санын табуу үчүн! , жөнөкөй жолу - н эсептөө! жана аягында канча нөл бар экендигин текшериңиз. Муну биз жөн эле, эгер санды 10го бөлгөндө, 0 калганын алабыз, андан кийин акыркы нөлдү 10го бөлүп алып, аны алып салабыз, ошондо биз ар бир жолу нөлгө барабар калгыча эсептей алабыз.

Бирок бул ыкма жөнөкөй бүтүн сандар менен иш жүзүндө колдонулбайт, анткени биз n билебиз! бул өтө чоң сан. C ++ жана Java тилдеринде жөнөкөй бүтүн сан 64-бит, ал бүтүн санды 2 ^ 63 - 1 чегинде гана сактай алат, болжол менен 10 ^ 18ге чейин. Java'да BigInteger классын колдонуп, 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дин санын табабыз.
Ошо сыяктуу эле, ушул сандагы 5тин санын табуу үчүн биз дагы бир нерсени жасайбыз.
Эми ушул эки эсептин минимумун кайтарып беребиз.

Бул иштейт, бирок биз аны бир аз оптималдаштыра алабыз. Бизде 1ден nге чейинки сандар бар экендигин анализдей алабыз, ошондуктан ар дайым 2 кубаттуулугун 5 күчүнөн көбүрөөк алмакпыз.
4кө чейин, бизде 2 саны (2 жана 4) болгон эки сан чыгат. 5те фактор болуп 5ке ээ болгон биринчи сан чыгат. Ошентип, бул окшош (көбөйүп жаткан) эсептөө айырмачылыгы менен улана берет. Төмөндө 2 фактор менен 5 фактордун ортосундагы тыгыздык кандайча айырмаланарын көрсөткөн визуалдаштыруу.

Factorial Trailing Zeroes Leetcode Solution

Демек, биз 2дин саны ар дайым 5те турган санга караганда көбүрөөк болот деген тыянак чыгарсак болот !.
Ошентип, биз 5тин гана санын табышыбыз керек жана анс болот. Ошентип, биз тапшырманы эки эсе кыскартабыз.

Factorial Trailing Zeroes Leetcode Solution үчүн ишке ашыруу

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

Factorial Trailing Zeroes Leetcode Solution үчүн комплекстүүлүктү талдоо

Убакыт татаалдыгы

O (n): биз бешке чейинки бардык көбөйткүчтөрдү кайталап жатабыз. Бештиктин санын табуу үчүн журнал (n) убакытты алып жаткан ар бир элемент үчүн окшош болушу мүмкүн. Бирок ал O (1) амортизациялайт, анткени биз текшерген сандардын көпчүлүгүндө бешөөнүн бир гана фактору бар. Демек, убакыттын жалпы татаалдыгы O (n) болуп кала берет.

Космостун татаалдыгы 

O (1): Эч кандай кошумча эс тутум колдонулбайт.

2-ыкма (5ти натыйжалуу эсептөө факторлору)

Жогоруда келтирилген ыкма боюнча, биз 5-тин эсебин берилген н фактору катары гана табышыбыз керек экендигин көрдүк. Жогорудагы ыкма боюнча, биз бардык 5 эселенген циклдерди карап чыгып, ар бир санга 5тин санын коштук жана сызыктуу убакытта жоопторубузду алдык. Логарифмалык убакытта анс-ты эсептөөгө мүмкүнчүлүк берген бир акыркы байкоо жүргүзөбүз.

Н! (б.а. 1ден nге чейин) бизде 5ке бөлүнбөгөн айрым сандар бар (0тин саны үчүн 5 салымы бар), андан кийин бизде 5ке бөлүнгөн бир нече сандар бар (ар бири бир эсептөө үчүн), андан кийин бизде бөлүнүүчү сандар бар 25 (бул жолу ушул көптөгөн сандардан кошумча кошумча салым), андан кийин 125ке бөлүнөт (булардан бир кошумча салым), ушул сыяктуу ж.б.у.с.

Ошондо биздин бардык ушул салымдардын суммасы болот.
Булардын бардыгын төмөндө келтирсек болот:
жалпы 5 саны = n / 5 + n / 25 + n / 125 +…. ж.б.
Бул бөлүүчүнүн nден кем болгонуна чейин барат, анткени андан кийин бөлүктүн интегралдык мааниси нөлгө барабар болот.

Step:
Бөлүштүрүүчү өзгөрмөнү 5 менен баштаңыз.
Run бир луп, ар бир кайталоодо n / бөлүүчү маанини кошуп, бөлүп алуучуну 5ке көбөйтүп, циклди бөлгүчкө чейин иштетип, <n.

Factorial Trailing Zeroes Leetcode Solution үчүн ишке ашыруу

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

Factorial Trailing Zeroes Leetcode Solution үчүн комплекстүүлүктү талдоо

Убакыт татаалдыгы

O (журнал (n)): бөлүп көрсөткүчтү 5ке көбөйткөн сайын, ал nден кем эмес. Демек, кайталоонун жалпы саны log (n) болот.

Космостун татаалдыгы 

O (1): Эч кандай кошумча эс тутум колдонулбайт.