USACO: Factorials

Problem Links:

USACO:Factorials,

Problem:

Factorials The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

PROGRAM NAME: fact4

INPUT FORMAT

A single positive integer N no larger than 4,220.

SAMPLE INPUT (file fact4.in)

7

OUTPUT FORMAT

A single line containing but a single digit: the right most non-zero digit of N! .

SAMPLE OUTPUT (file fact4.out)

4

Solution:

They only factor could result rear zeros is the product of 2 and 5,(10 could be handled as 2 * 5).
So we count the number of 2s and 5s, obviously 2s are much more than 5s as you can see.

We keep multiply numbers, resulted by removing 2s and 5s, while counting the number of 2s and 5s.
At last, get the final result with 2s and 5s. Check out the code for details.

Source Code:

/*
 ID: ***
 TASK: fact4
 LANG: JAVA
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

public class fact4 {

        public static void main(String[] args) throws Exception {
                fact4 main = new fact4();
                main.run();
                System.exit(0);
        }

        private void run() throws Exception {
                BufferedReader br = new BufferedReader(new FileReader("fact4.in"));
                PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
                                "fact4.out")));

                int N = Integer.parseInt(br.readLine());
                br.close();
                int cnt2 = 0;
                int cnt5 = 0;
                int prod = 1;
                for (int i = 1; i <= N; i++) {
                        int tmp = i;
                        while (tmp % 2 == 0) {
                                tmp /= 2;
                                cnt2++;
                        }
                        while (tmp % 5 == 0) {
                                tmp /= 5;
                                cnt5++;
                        }
                        prod = (prod * tmp) % 10;
                }

                if (cnt2 == cnt5)
                        out.write(Integer.toString(prod));
                else if (cnt2 > cnt5) {
                        for (int i = 0; i < cnt2 - cnt5; i++)
                                prod = (prod * 2) % 10;
                        out.write(Integer.toString(prod));
                } else {
                        for (int i = 0; i < cnt5 - cnt2; i++)
                                prod = (prod * 5) % 10;
                        out.write(Integer.toString(prod));
                }
                out.write("\n");

                out.close();
        }
}