Оптимизирующий код, чтобы найти единичную цифру факториала данного числа N

Question

Я попробовал вопрос из конкурса, точное утверждение которого выглядит так:

Given a number N. The task is to find the unit digit of factorial of given 
number N.

Input:
First line of input contains number of testcases T. For each testcase, there 
will be a single line containing N.

Output:
For each testcase, print the unit digit of factorial of N.

Constraints:
1 <= T <= 1000
1 <= N <= 1018 

и придумал следующий код:

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) throws IOException{
     BufferedReader reader =  
               new BufferedReader(new InputStreamReader(System.in)); 
    int cases = Integer.parseInt(reader.readLine());
    int i=0;
    while(i<cases){
        fact(Integer.parseInt(reader.readLine()));i++;
    }
}

static void fact(int num){
    int j,fact=1;     
    for(j=1;j<=num;j++){    
        fact=fact*j;    
        }  
        System.out.println(fact%10);
   }
}

Это дает правильный вывод при выполнении с пользовательскими входами, но когда все тестовые примеры перепробованы, оно дает: «ПРЕДЕЛ ВРЕМЕНИ ПРЕВЫШЕН. Оптимизируйте свой код» . Я пытался использовать bufferedReader вместо класса Scanner, но безрезультатно. Я не мог узнать, как я мог оптимизировать этот код дальше. Я что-то пропустил?

Answer 1

Разница между BufferedReader и Scanner, вероятно, здесь не будет заметна. Если вы сравните свой код, вы, вероятно, обнаружите, что самая тяжелая его часть - это факторный расчет. Я не могу придумать более быстрый способ его вычисления, но здесь уловка, которая вам, вероятно, не нужна.

Давайте рассмотрим первые несколько факториалов:

• 0! = 1 -> Единица измерения 1
• 1! = 1 -> Единица измерения - 1
• 2! = 2 -> Единица измерения: 2
• 3! = 6 -> Единица измерения - 6
• 4! = 24 -> Единица измерения 4
• 5! = 120 -> Единица измерения 0

Любой факториал, равный 6 или больше, будет представлять собой натуральные целые числа, умноженные на 5! кеш всех опций вместо расчета факториала каждый раз. E.g.:

// The index is the factorial to be calculated, the value is the unit digit:
private static final int[] UNITS = new int[] {1, 1, 2, 6, 4};

private static void fact(int f) {
    int unit = 0;
    if (f <= 4) {
        unit = UNITS[f];
    }
    System.out.println(unit);
}

Answer 2

Вам не нужно вычислять факториалы для этой проблемы. Цифра единиц fact(n) будет 0 для n > 4. (Я бы сделал небольшую таблицу для других возможных входов.)