Optimising code to find the unit digit of factorial of given number N

user_10898466 0
Viewed 1400

I tried a question from a contest whose exact statement is like this:

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

and came up with following code:

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);
   }
}

It gives right output when executed with custom inputs but when all test cases are tried it gives:"TIME LIMIT EXCEEDED. Optimise your code". I tried to use bufferedReader instead of Scanner class but to no effect. I could not find out how could I optimise this code further. Is there anything I am missing?

factorial algorithm java performance
2 Answers

The difference between BufferedReader and Scanner probably won't be noticeable here. If you benchmark your code you'll probably find that the heaviest part of it the factorial calculation. Offhand, I can't think of a faster way to calculate it, but the trick here that you probably don't have to.

Let's examine the first few factorials:

  • 0! = 1 -> Unit digit is 1
  • 1! = 1 -> Unit digit is 1
  • 2! = 2 -> Unit digit is 2
  • 3! = 6 -> Unit digit is 6
  • 4! = 24 -> Unit digit is 4
  • 5! = 120 -> Unit digit is 0

Any factorial of 6 or larger would be some natural integers multiplied by 5!, which is 120. So, no matter what they are, the unit digit will be 0. With such a small data set, you can just create a cache of all the options instead of calculating the factorial each time over. 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);
}
user_24227760

You don't have to compute factorials for this problem. The units digit of fact(n) is going to be 0 for n > 4. (I'd make a small table for the other possible inputs.)

Bill_the_Lizard_12880
Related