Write an algorithm which computes the number of trailing zeros in n factorial

This looks like a brain teaser question, but it can be approached logically. Every 0 will come from a 2 and a 5, so we only need to count the number of 2 and 5 pairs in the factorial, there are more 2s than 5s so we only need to count the number of 5. Given the example of 31, for those who has one 5 has factor, we will have 5, 10, 15, 20, 30, and 25 will have 2 fives, so we will have 7 0s at the end of the 31!

	public static int zeroFactorial(int num) {
		int count = 0;
		for (int i = 1; i <= num; i++) {
			//count number of 5 in each element
			int element = i;
			while(element > 0 && element % 5 == 0) {
				element /= 5;
				count++;
			}
		}
		return count;
	}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s