Factorial Trailing Zeroes Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Bloomberg
Մաթեմատիկա

Խնդիրի հայտարարություն

Այս խնդրում մենք պետք է պարզենք, թե քանի հետևող զրո կլինի n- ում:
Որպես մուտքագրում տրված է n:

Ինչպես 5-ում կա մեկ զրո հետք:
հինգ! = 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 գործոնի խտությունը:

Factorial Trailing Zeroes Leetcode լուծում

Հետևաբար, կարող ենք եզրակացնել, որ 2-ի հաշվարկը միշտ ավելի մեծ է, քան n- ում `5-ի:
Այսպիսով, մենք պետք է գտնենք միայն 5-ի հաշվարկը, և դա կլինեն պատասխանները: Այս կերպ մենք առաջադրանքը կիսով չափ կրճատում ենք:

Իրականացում Factorial Trailing Zeroes 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 լուծման համար

Timeամանակի բարդություն

Վրա) : մենք կրկնում ենք հինգի բոլոր բազմապատկածները մինչև n: Կարող է թվալ, որ յուրաքանչյուր տարրի համար մենք մուտք ենք գործում (n) ժամանակ ՝ հնգյակների հաշվարկը գտնելու համար: Բայց դա ամորտիզացվում է O (1) –ի համար, քանի որ մեր կողմից ստուգված թվերի ճնշող մեծամասնությունը պարունակում է միայն հինգ գործոն: Հետևաբար, ընդհանուր ժամանակի բարդությունը մնում է O (n):

Տիեզերական բարդություն 

O (1): Ոչ մի լրացուցիչ հիշողություն չի օգտագործվում:

Մոտեցում 2 (արդյունավետորեն հաշվարկելով 5-ը)

Վերոնշյալ մոտեցման մեջ մենք տեսանք, որ մենք պետք է 5-ի հաշվարկը գտնենք միայն որպես տրված n- ի գործոն: Վերը նշված մոտեցման մեջ մենք շրջանցեցինք 5-ի բոլոր բազմապատիկները և յուրաքանչյուր թվի համար ավելացրեցինք 5-ի հաշիվը և ստացանք մեր պատասխանները գծային ժամանակում: Մենք կկատարենք մեկ վերջնական դիտարկում, որը թույլ կտա մեզ հաշվել ANS- ը լոգարիթմական ժամանակում:

Պանդոկ! (այսինքն ՝ 1-ից n) մենք ունենք մի քանի թվեր, որոնք չեն բաժանվում 5-ի (նպաստելով 0-ի 5-ի հաշվարկի համար), ապա ունենք որոշ թվեր, որոնք բաժանվում են 5-ի (յուրաքանչյուրը նպաստում է մեկ հաշվարկի), ապա ունենք թվեր, որոնք բաժանվում են ըստ 25 (այս անգամ մեկ ավելացված ներդրում այս բազմաթիվ թվերից), այնուհետև բաժանվում է 125-ի վրա (դրանցից մեկ հավելյալ ներդրում), ինչպես սա և այլն:

Այդ դեպքում մեր պատասխանները կլինեն այս բոլոր ներդրումների գումարը:
Այս ամենը կարող ենք ամփոփել ինչպես ստորև.
5-ի ընդհանուր քանակը = n / 5 + n / 25 + n / 125 +: այսպես շարունակ
Սա գնալու է մինչ հայտարարը n- ից փոքր է, քանի որ դրանից հետո կոտորակի ինտեգրալ արժեքը զրո կլինի:

Քայլ:
Նախաձեռնեք հայտարարի փոփոխականը 5-ով:
Run a հանգույց, յուրաքանչյուր կրկնության մեջ ավելացրեք n / հայտարարի արժեք արդյունքին և հայտարարը բազմապատկեք 5-ով: Գործարկեք օղակը մինչ հայտարարը <n:

Իրականացում Factorial Trailing Zeroes 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 լուծման համար

Timeամանակի բարդություն

O (տեղեկամատյան (n)): մենք ամեն անգամ հայտարարը բազմապատկում ենք 5-ով, մինչև այն n- ից պակաս լինի: Հետևաբար, կրկնության ընդհանուր քանակը կգրանցվի (n):

Տիեզերական բարդություն 

O (1): Ոչ մի լրացուցիչ հիշողություն չի օգտագործվում: