Рубрики

Подсчет конечных нулей в факториале числа

Получив целое число n, напишите функцию, которая возвращает число конечных нулей в n !.

Примеры :

Input: n = 5
Output: 1 
Factorial of 5 is 120 which has one trailing 0.

Input: n = 20
Output: 4
Factorial of 20 is 2432902008176640000 which has
4 trailing zeroes.

Input: n = 100
Output: 24

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простой метод состоит в том, чтобы сначала вычислить факториал n, а затем посчитать конечные 0 в результате (мы можем посчитать конечные 0, многократно разделив факториал на 10, пока остаток не станет 0).

Вышеупомянутый метод может вызвать переполнение для немного больших чисел, так как факториал числа является большим числом (см. Факториал числа 20, приведенный в приведенных выше примерах). Идея состоит в том, чтобы рассмотреть основные факторы факториала n. Конечный ноль всегда получается простыми множителями 2 и 5. Если мы можем посчитать число 5 и 2, наша задача выполнена. Рассмотрим следующие примеры.

n = 5: есть 5 и 3 2 в простых множителях 5! (2 * 2 * 2 * 3 * 5). Таким образом, число конечных 0 равно 1.

n = 11: есть два 5 и три 2 в простых множителях 11! (2 8 * 3 4 * 5 2 * 7). Таким образом, число конечных 0 равно 2.

Мы можем легко заметить, что число 2s в простых множителях всегда больше или равно числу 5s. Так что, если мы посчитаем 5 в основных факторах, мы закончили. Как посчитать общее число 5s в простых множителях n !? Простой способ — рассчитать пол (n / 5). Например, 7! имеет 5, 10! имеет две 5 с. Это сделано еще, есть еще одна вещь, чтобы рассмотреть. Числа, такие как 25, 125 и т. Д., Имеют более одного 5. Например, если мы рассмотрим 28 !, мы получаем одну лишнюю 5, а число 0 становится 6. Обработка этого проста, сначала разделим n на 5 и удалим все одиночные 5, а затем разделите на 25, чтобы удалить лишние 5 с и так далее. Ниже приводится обобщенная формула для подсчета конечных 0.

Trailing 0s in n! = Count of 5s in prime factors of n!
                  = floor(n/5) + floor(n/25) + floor(n/125) + ....

Ниже приведена программа на основе приведенной выше формулы.

C ++

// C ++ программа для подсчета
// концевые 0 в n!
#include <iostream>

using namespace std;

  
// Функция для возврата трейлинга
// 0 в факториале n

int findTrailingZeros(int n)

{

    // Инициализировать результат

    int count = 0;

  

    // Продолжаем делить n на степени

    // 5 и счетчик обновлений

    for (int i = 5; n / i >= 1; i *= 5)

        count += n / i;

  

    return count;

}

  
// Код драйвера

int main()

{

    int n = 100;

    cout << "Count of trailing 0s in " << 100

         << "! is " << findTrailingZeros(n);

    return 0;

}

Джава

// Java-программа для подсчета
// концевые 0 в n!

import java.io.*;

  

class GFG 

{

    // Функция для возврата трейлинга

    // 0 в факториале n

    static int findTrailingZeros(int n)

    {

        // Инициализировать результат

        int count = 0;

  

        // Продолжаем делить n на степени

        // из 5 и счетчик обновлений

        for (int i = 5; n / i >= 1; i *= 5)

            count += n / i;

  

        return count;

    }

      

    // Код драйвера

    public static void main (String[] args) 

    {

        int n = 100;

        System.out.println("Count of trailing 0s in "

                                           n +"! is "

                                 findTrailingZeros(n));

    }

}

  
// Этот код предоставлен Pramod Kumar

python3

# Python3 программа для
# количество завершающих 0
# гостиница!

  
# Функция для возврата
# конечные 0 в
# факториал n

def findTrailingZeros(n):

      

    # Инициализировать результат

    count = 0

  

    # Продолжай делить на

    # полномочия 5 и

    # update Count

    i=5

    while (n/i>=1):

        count += int(n/i)

        i *= 5

  

    return int(count)

  
# Драйверная программа

n = 100

print("Count of trailing 0s "+

    "in 100! is",findTrailingZeros(n))

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для подсчета
// концевые 0 в n!

using System;

  

class GFG 

{

      

    // Функция для возврата трейлинга

    // 0 в факториале n

    static int findTrailingZeros(int n)

    {

        // Инициализировать результат

        int count = 0;

  

        // Продолжаем делить n на степени

        // из 5 и счетчик обновлений

        for (int i = 5; n / i >= 1; i *= 5)

            count += n / i;

  

        return count;

    }

      

    // Код драйвера

    public static void Main () 

    {

        int n = 100;

        Console.WriteLine("Count of trailing 0s in "

                                           n +"! is "

                                findTrailingZeros(n));

    }

}

  
// Этот код предоставлен vt_m

PHP

<?php
// PHP-программа для подсчета
// концевые 0 в n!

  
// Функция для возврата трейлинга
// 0 в факториале n

function findTrailingZeros( $n)

{

    // Инициализировать результат

    $count = 0;

  

    // Продолжаем делить n на степени

    // из 5 и счетчик обновлений

    for ($i = 5; $n / $i >= 1; $i *= 5)

        $count += $n / $i;

  

    return $count;

}

  
// Код драйвера

  

$n = 100;

echo "Count of trailing 0s in " , 100, 

     "! is " , findTrailingZeros($n);

  
// Этот код предоставлен vt_m
?>

Выход :

Count of trailing 0s in 100! is 24 

Эта статья пополняемая Рахул Джейна. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчет конечных нулей в факториале числа

0.00 (0%) 0 votes