Skip to code
Skip to analysis

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

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

CODE

Java

C++

Pascal

ANALYSIS

Russ Cox

The insight for this problem is that 0’s at the end of a number come from it being divisible by 10, or equivalently, by 2 and 5. Furthermore, there are always more 2s than 5s in a factorial.

To get the last digit of the factorial, we can run a loop to calculate it modulo 10, as long as we don’t include any 2s or 5s in the product. Of course, we want to exclude the same number of 2s and 5s, so that all we’re really doing is ignoring 10s. So after the loop, we need to multiply in any extra 2s that didn’t have 5s to cancel them out.

/*
PROG: fact4
ID: rsc001
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void
main(void)
{
	FILE *fin, *fout;
	int n2, n5, i, j, n, digit;

	fin = fopen("fact4.in", "r");
	fout = fopen("fact4.out", "w");
	assert(fin != NULL && fout != NULL);

	fscanf(fin, "%d", &n);
	digit = 1;
	n2 = n5 = 0;
	for(i=2; i<=n; i++) {
		j = i;
		while(j%2 == 0) {
			n2++;
			j /= 2;
		}
		while(j%5 == 0) {
			n5++;
			j /= 5;
		}
		digit = (digit * j) % 10;
	}

	for(i=0; i<n2-n5; i++)
		digit = (digit * 2) % 10;

	fprintf(fout, "%d\n", digit);
	exit(0);
}

Back to top