## Thursday, February 21, 2013

### USACO: Factorials

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.

### INPUT FORMAT

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

```7
```

### OUTPUT FORMAT

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

`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: ***
LANG: JAVA
*/
import java.io.BufferedWriter;
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 {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"fact4.out")));

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