Найти первое ненулевое число в N! на Яве

Question

Как найти первое ненулевое число факториала N. N может быть в диапазоне от 1 до 2147483647. Выходные данные возвращают целое число.

EX:

findFirstNoneZeroNumberOfTheFactorial(4) = 4; // because 4! = 24
findFirstNoneZeroNumberOfTheFactorial(5) = 2; // because 5! = 120

вот мой код:

import java.math.BigInteger;

public class Solution {
    public static int findFirstNoneZeroNumberOfTheFactorial(int n) {
        BigInteger fact = null;
        for (int i = 1; i <= n; i++) {
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        String sFact = String.valueOf(fact);
        for (int i = sFact.length() - 1; i >= 0; i--) {
            if (sFact.charAt(i) != '0') {
                int result = Character.getNumericValue(sFact.charAt(i));
                return result;
            }
        }
        return 0;
    }
    public static void main(String[] args){
        System.out.println(Solution.findFirstNoneZeroNumberOfTheFactorial(4));
    }
}

Но это не работает!!

Answer 1

Ваша инициализация неверна.

BigInteger fact = BigInteger.ONE;

Это не оптимально. Если вам нужна только одна последняя ненулевая цифра, просто отслеживайте только последнюю ненулевую цифру, а не все умноженное число.

let's do some math
x     x!      last-nonzero-digit(x * last-nonzero-digit)
1     1             1*1        => 1
2     2             2*1 = 2    => 2
3     6             3*2 = 6    => 6 
4     24            6*4 = 2(4) => 4
5     120           4*5 = (2)0 => 2 
6     720           2*6 = 1(2) => 2
7     5040          2*7 = 1(4) => 4

ПОЧЕМУ Я ДОЛЖЕН РАССЧИТАТЬ ВЕСЬ МУЛЬТИПЛИКАЦИЮ?

Просто сохраните последнюю ненулевую цифру.

Answer 2

Вы забыли инициализировать свой fact переменная, которая приводит к NullPointerException,

+ Изменить

BigInteger fact = null;

в

BigInteger fact = BigInteger.ONE;

Выход для System.out.println(Solution.findFirstNoneZeroNumberOfTheFactorial(4));:

4

Answer 3

Вместо того, чтобы преобразовать его в проверку строки для работы модуля, и если он отличается от нуля, это ваш ответ, в противном случае разделите на 10.

public static int findFirstNoneZeroNumberOfTheFactorial(int n) {
    long fact = 1L;
    for (int i = 1; i <= n; i++) {
        fact = fact * i;
    }
    while (fact > 0) {
        long module = fact % 10;
        if (module != 0) {
            return module;
        }
        fact = fact / 10;
    }
    return -1;

}

Answer 4

Это правильно??

public static int number(int n) {
        int LastNoneZero = 1;
        for (int i = 1; i <= n; i++) {
            LastNoneZero *= i;
            if (LastNoneZero > 9) {
                String s = Integer.toString(LastNoneZero);
                if (s.charAt(1) == '0') {
                    LastNoneZero = Character.getNumericValue(s.charAt(0));
                } else {
                    LastNoneZero = Character.getNumericValue(s.charAt(1));
                }
            }
        }
        return LastNoneZero;
    }