Faktorial Arxa Sıfır Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Bloomberg
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 37

Problem bəyanat

Bu problemdə n-də nə qədər arxada sıfır olacağını öyrənməliyik!
Giriş olaraq n verilmişdir.

5-də bir son sıfır olduğu kimi!
5! = 5 * 4 * 3 * 2 * 1 = 120

misal

n = 3
0

İzahat: 3! = 6, sıfır yoxdur

n = 0
0

İzahat: 0! = 1, sıfır yoxdur

 

N-də son sıfırların sayını tapmaq üçün! , sadə bir yol n hesablamaqdır! və sonunda neçə sıfır olduğunu yoxlayın. Bunu sadəcə ədədi 10-a bölməyimizi yoxlamaqla 0 qalıq əldə etdikdən sonra son sıfırı 10-a bölməklə çıxarmaqla edə bilərik. Hər dəfə sıfıra bərabər qalıq əldə edənə qədər bunu saya bilərik.

Ancaq bu yanaşma sadə tam ədədlərlə praktik deyil, çünki n bilirik! çox böyük rəqəmdir. C ++ və Java-da sadə tam ədədi ən yaxşı halda 64 bitdir, yalnız bir ədədi 2 ^ 63 - 1 həddində saxlaya bilər. Bu, təxminən 10 ^ 18-ə bərabərdir. Java-da n !. kimi böyük rəqəmləri saxlamaq üçün BigInteger sinifindən istifadə edə bilərik. Ancaq bu kobud güc yanaşması böyük zaman və məkan mürəkkəbliyinə malikdir.

Burada n-də arxada qalan sıfırları tapmaq üçün səmərəli həlli müzakirə edəcəyik!

Yanaşma 1 (5 sayma amili)

Ardıcıl sıfırların ümumi sayının, 10-un bu sayın neçə dəfə olduğunu hesablamaqla bərabər olacağını deyə bilərik. Və bilirik ki, hər 10 hər iki əsas say 2 və 5-in məhsulundan əmələ gəlir.
Beləliklə, sayda 2-nin neçə amilinin olduğunu öyrənsək. Eynilə 5-lərin neçə amili var. Bundan sonra bunların hər birinin birləşərək məhsulu 10-a bərabər edəcəyini söyləyə bilərik. Buna görə arxadakı sıfırların ümumi sayı minimuma bərabər olacaq (2-nin sayı, 5-in sayı).

İndi bu faktorları n !.
n! = 1 * 2 * 3… .. * (n-1) * n

Beləliklə, 2-dən n-ə qədər olan bütün rəqəmlər üzərində təkrarlanacağıq (ən azı 2-ni ehtiva edən rəqəmlər olduğu üçün 2-yə artaraq).
Hər ədədə görə 2-yə bölünənə qədər 2-yə böləcəyik ki, bu ədədin faktorizasiyasında 2-nin sayını tapaq.
Eynilə bu sayda 5-lərin sayını tapmaq üçün eyni şeyi edəcəyik.
İndi bu iki saydan minimumu qaytaracağıq.

Bu işləyir, amma bir az da optimize edə bilərik. 1-dən n-ə qədər rəqəmlər olduğumuzu təhlil edə bilərik ki, hər zaman 2-nin güclərini 5-dən daha çox gücə sahib olardıq.
4-ə kimi biz də 2-yə bərabər olan iki ədədi alırıq (2 və 4). 5-də faktor kimi 5-ə bərabər ilk rəqəmi alırıq. Beləliklə, bu oxşar (artan) say fərqi ilə davam edəcəkdir. Budur 2 amil ilə 5 amil arasındakı sıxlığın necə fərqləndiyini göstərən bir əyani görüntü.

Faktorial Arxa Sıfır Leetcode HəlliPin

Buna görə 2-nin sayının həmişə n-də 5-dən daha çox olduğu qənaətinə gələ bilərik.
Beləliklə, yalnız 5-lərin sayını tapmaq lazımdır və bu ans olacaq. Bu şəkildə tapşırığı yarıya endiririk.

Faktorial Arxa Sıfır Leetcode Həlli üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Faktorial Arxa Sıfır Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n): n-ə qədər bütün beşliklərin çoxu üzərində təkrar edirik. Beşlərin sayını tapmaq üçün log (n) vaxt götürdüyümüz hər bir element üçün belə görünə bilər. Ancaq O (1) ilə amortizasiya olunur, çünki yoxladığımız rəqəmlərin böyük əksəriyyətində yalnız beşlik faktoru var. Beləliklə, ümumi zaman mürəkkəbliyi O (n) olaraq qalır.

Kosmik Mürəkkəblik 

O (1): Əlavə yaddaş istifadə olunmur.

Yanaşma 2 (Səmərəli 5 sayma faktorları)

Yuxarıda göstərilən yanaşmada 5-lərin sayını yalnız verilmiş n !. Yuxarıdakı yanaşmada biz 5-in bütün vurmalarının üstündən keçdik və hər bir rəqəm üçün 5-lər əlavə etdik və xətti vaxtda anslarımızı əldə etdik. Loqaritmik vaxtda ans hesablamağımıza imkan verən bir son müşahidəni aparacağıq.

Mehmanxana! (yəni 1-dən n-ə qədər) 5-ə bölünməyən bəzi nömrələrimiz var (0-lərin sayına 5 qatqı veririk), onda 5-ə bölünən bəzi nömrələrimiz var (hər biri bir saymağa kömək edir), sonra bölünən nömrələrimiz var 25 (bu dəfə bu çox saydan bir əlavə töhfə), sonra 125-ə bölünür (bunlardan bir əlavə töhfə), bu kimi və s.

O zaman bizim ans bu bütün töhfələrin cəmi olacaqdır.
Bütün bunları aşağıdakı kimi ümumiləşdirə bilərik:
5-nin ümumi sayı = n / 5 + n / 25 + n / 125 +…. və s
Bu məxrəc n-dən az olana qədər gedəcək, çünki bundan sonra kəsrin inteqral dəyəri sıfır olacaqdır.

Addım:
Məxrəc dəyişkənini 5 ilə başlayın.
Run a loop, hər təkrarlamada məxrəcin nəticəsi və 5-ə vurulması üçün n / məxrəc dəyəri əlavə edin. Döngəni məxrəc <n-ə qədər çalıştırın.

Faktorial Arxa Sıfır Leetcode Həlli üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

#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

Faktorial Arxa Sıfır Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (log (n)): hər dəfə məxrəci n-dən az olana qədər 5-ə vururuq. Beləliklə, təkrarlamanın ümumi sayı log (n) olacaqdır.

Kosmik Mürəkkəblik 

O (1): Əlavə yaddaş istifadə olunmur.

Şərh yaz

Translate »
1