优化代码以找到给定数量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!,即120.所以,无论它们是什么,单位数字都是0.使用如此小的数据集,你可以创建一个全部的缓存选项而不是每次计算阶乘.例如:

// 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.(我会为其他可能的输入做一个小桌子.)