Ҳалли сифрҳои Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Блумберг
Матем

Изҳороти мушкилот

Дар ин мушкилот, мо бояд фаҳмем, ки дар n чанд сифрҳои қафо мавҷуданд!
Н ҳамчун вуруд дода шудааст.

Монанди он аст, ки дар як сифр паси дар 5!
5! = 5 * 4 * 3 * 2 * 1 = 120

мисол

n = 3
0

Шарҳ: 3! = 6, ҳеҷ сифри қафо нест

n = 0
0

Шарҳ: 0! = 1, ҳеҷ сифри қафо нест

 

Барои пайдо кардани шумораи сифрҳои қафо дар 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).

Ҳоло мо бояд ин омилҳоро дар н !.
н! = 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 ҳамеша аз ҳисоби 5 дар n бузургтар аст!.
Пас, мо бояд танҳо 5-ро ҳисоб кунем ва ин анс хоҳад буд. Бо ин роҳ мо супоришро нисф кам мекунем.

Татбиқи ҳалли Zeroes Leetcode Factorial Trailing

Барномаи 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

Таҳлили мураккабӣ барои ҳалли Zeroes Leetcode Factorial Trailing

Мураккабии вақт

O (n): мо дар тамоми зарбҳои панҷ то н такрор мешавем. Ин метавонад барои ҳар як унсуре, ки мо вақти (n) вақти ҷустуҷӯро барои ёфтани миқдори панҷгона мегирем, монанд бошад. Аммо он ба O (1) амортиза мекунад, зеро аксарияти рақамҳои санҷидашуда танҳо як омили панҷ иборатанд. Аз ин рӯ, мураккабии умумии вақт ҳамчун O (n) боқӣ мемонад.

Мураккабии фазо 

О (1): Ягон хотираи иловагӣ истифода намешавад.

Равиши 2 (Омилҳои ҳисобкунии 5 самаранок)

Дар равиши дар боло овардашуда мо дидем, ки мо бояд ҳисобҳои 5-ро танҳо ҳамчун як омили додашудаи н !. Дар ин равиши боло мо ҳамаи зарбҳои 5-ро давр зада баромадем ва барои ҳар як рақам 5-ро илова кардем ва дар вақти хаттӣ ҷавобҳои худро гирифтем. Мо як мушоҳидаи ниҳоӣ хоҳем кард, ки ба мо имкон медиҳад, ки ансҳоро дар вақти логарифм ҳисоб кунем.

Меҳмонхона! (яъне аз 1 то n) мо якчанд адад дорем, ки ба 5 тақсим карда намешаванд (0 барои ҳисоби 5 ҳисса мегузоранд), пас мо якчанд ададе дорем, ки ба 5 тақсим карда мешавад (ҳар кадоме як ҳисобро тақсим мекунад), он гоҳ рақамҳое дорем, ки бо тақсим мешаванд 25 (ин дафъа як саҳми иловагӣ аз ин шумораи зиёд), пас ба 125 тақсим карда мешавад (як саҳми иловагӣ аз инҳо), ба монанди ин ва ғайра.

Он гоҳ ансамбли мо маҷмӯи ҳамаи ин саҳмҳо хоҳад буд.
Мо ҳамаи инҳоро дар зер ҷамъбаст карда метавонем:
шумораи умумии 5s = n / 5 + n / 25 + n / 125 +…. ва ғайра
Ин то он даме хоҳад шуд, ки ҷудошаванда аз n камтар бошад, зеро пас аз ин арзиши интегралии каср ба сифр баробар мешавад.

Қадам:
Тағирёбандаи махрумро бо 5 оғоз кунед.
А Давр, дар ҳар такрори арзиши n / махраҷро барои натиҷа додан ва коҳишро ба 5 зарб кардан илова кунед. Доираро то коди коҳиш <n иҷро кунед.

Татбиқи ҳалли Zeroes Leetcode Factorial Trailing

Барномаи 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

Таҳлили мураккабӣ барои ҳалли Zeroes Leetcode Factorial Trailing

Мураккабии вақт

O (log (n)): мо ҳар дафъа зарбро то 5 зиёд мекунем, то он даме ки аз n камтар шавад. Аз ин рӯ, шумораи умумии такрор log (n) хоҳад буд.

Мураккабии фазо 

О (1): Ягон хотираи иловагӣ истифода намешавад.