Сколько нулей в конце у факториала

175

06 февраля 2022, 23:20

Условие :

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

N! = 1 * 2 * 3 * ... * N

Be careful 1000! has 2568 digits...

For more info, see: http://mathworld.wolfram.com/Factorial.html

Examples

zeros(6) = 1
6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 trailing zero
zeros(12) = 2
12! = 479001600 --> 2 trailing zeros

Hint: You're not meant to calculate the factorial. Find another way to find the number of zeros.

Как мы видим в последней строчке, вычислять факториал не требуется. Но для понимания картины я решил это сделать.

 public static int zeros(int n) {

        BigInteger x = BigInteger.ONE;
        BigInteger temp = BigInteger.ONE;
        while (!x.toString().equals(String.valueOf(n)))
         {
            temp = temp.multiply(x);
            x = x.add(BigInteger.ONE);
         }
        System.out.println(temp);
        String tempStr = String.valueOf(temp);
        int countZero = 0;
        for(int i = 0 ; i < tempStr.length() ; i ++){
            countZero = tempStr.charAt(i)=='0' ? countZero+1 : 0;
        }
        return countZero;
    }

Пробуем N = 1000;

Результат : 246. На мой взгляд решение верное (по условию), но ответ неверный. Должно быть 249. Стал копать.

Наткнулся на это

https://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/

Ну и ниже решение :

static int findTrailingZeros(int n) 
    { 
        // Initialize result 
        int count = 0; 
        // Keep dividing n by powers  
        // of 5 and update count 
        for (int i = 5; n / i >= 1; i *= 5) 
            count += n / i; 
        return count; 
    }

Пожалуйста, помогите разобраться почему мой код не верен, и что написано в пояснении к решению задачи?

Answer 1

У вас ошибка в вычислении факториала: вы не умножаете на само число n. У вас цикл, пока х не равен n, а n тоже участвует в умножении. Вот исправленный вариант. Все-таки разумно разделить вычисление факториала и подсчет нулей.

Вычисление факториала

public static String factorial(int n){
        BigInteger x = BigInteger.ONE;
        BigInteger temp = BigInteger.ONE;
        int i=1;
        while (i<=n)
         {
            temp = temp.multiply(x);
            x = x.add(BigInteger.ONE);
            i++;
         }
         return temp.toString();
    }

Подсчет нулей с ним тоже у вас проблемы, так как считать надо с конца строки.

   public static int zeros(String number){
        int i=number.length()-1;
        int res=0;
        while (number.charAt(i)=='0'&&i>=0){
            res++;
            i--;
        }
         return res;
    }

Алгоритм основан на основной теореме арифметики. Нулей будет min(количество 2,количество 5) в разложении числа по степеням простых делителей. Так как очевидно, что 5 в факториале встречается реже, то можно подсчитать только количество 5.

Answer 2

А вам это интересно.. Для чего вам вам, нули в центре, если они вам нужны только в конце. Или, количество нулей так''же зависит от количества десятков использованных при получении к! или к, чисел 5. А ещё, на такие числа как, (25 !); (100)! (50 !) (225)! (125 !) 175! Также, понадобить добавлять дополнительные нули на конце, ещё, а, это всё-таки можете проверить. Это всё