Рішення Faetorial Trailing Zeroes Leetcode


Рівень складності Легко
Часто запитують у Bloomberg
Математика

Постановка проблеми

У цій задачі ми повинні з’ясувати, скільки кінцевих нулів буде в n!
Дано n як вхідні дані.

Начебто є один нуль у 5!
5! = 5 * 4 * 3 * 2 * 1 = 120

Приклад

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 !.
п! = 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 факторами відрізняється.

Рішення Faetorial Trailing Zeroes Leetcode

Тому ми можемо зробити висновок, що рахунок 2 завжди більше, ніж рахунок 5 у n !.
Отже, нам потрібно знайти підрахунок лише 5, і це буде відповідь. Таким чином ми зменшуємо завдання вдвічі.

Впровадження рішення Factorial Trailing Zeroes Leetcode

Програма С ++

#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

Аналіз складності для розв'язування нульових нулів факторіального рішення

Складність часу

O (n): ми перебираємо всі кратні від п’яти до n. Може виглядати так, що для кожного елемента, на який ми витрачаємо log (n) час, знаходимо рахунок п’яти. Але воно амортизується до O (1), оскільки переважна більшість перевірених нами чисел містить лише один коефіцієнт п’ять. Отже, загальна складність часу залишається такою, як O (n).

Складність простору 

O (1): Не використовується додаткова пам'ять.

Підхід 2 (підрахування коефіцієнтів 5 ефективно)

У наведеному вище підході ми побачили, що нам потрібно знайти рахунок 5-х лише як коефіцієнт даного n !. У наведеному вище підході ми прокрутили всі кратні 5 і додали рахунок 5 для кожного числа і отримали відповіді за лінійний час. Ми зробимо одне остаточне спостереження, яке дозволить нам розрахувати анс за логарифмічним часом.

Готель! (тобто від 1 до n) ми маємо кілька чисел, які не діляться на 5 (вносячи 0 в рахунок 5), тоді ми маємо деякі числа, які діляться на 5 (кожен вносить один рахунок), тоді ми маємо числа, які діляться на 25 (на цей раз один додатковий внесок із цих багатьох чисел), потім ділиться на 125 (один додатковий внесок з них), як це тощо.

Тоді наші анни будуть сумою всіх цих внесків.
Ми можемо підсумувати все це, як показано нижче:
загальна кількість 5 = ​​n / 5 + n / 25 + n / 125 +…. так далі
Це триватиме доти, доки знаменник не стане менше n, оскільки після цього інтегральне значення частки буде дорівнювати нулю.

Крок:
Ініціалізуйте змінну знаменника за допомогою 5.
Запустіть a петля, у кожній ітерації додайте значення n / знаменника, щоб отримати і помножте знаменник на 5. Запустіть цикл до знаменника <n.

Впровадження рішення Factorial Trailing Zeroes Leetcode

Програма С ++

#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

Аналіз складності для розв'язування нульових нулів факторіального рішення

Складність часу

O (log (n)): ми множимо знаменник на 5 щоразу, поки воно не буде менше n. Отже, загальна кількість ітерацій буде log (n).

Складність простору 

O (1): Не використовується додаткова пам'ять.