number of trailing zeros in a factorial

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

My initial thoughts:
The trailing zeros are constructed by pairs of 2 and 5. So to count the number of trailing zeros, we need to count the number of pairs of 2 and 5. For a factorial, there are way more number of factor 2 than 5 so we just need to count the number of factor 5 in the factorial. The factor 5 is constructed by 5, 5^2, 5^3, etc. For example, there is only 1 factor 5 (5 itself) in 5! so there is only 1 trailing zero. There are 3 factor 5 (5, 10 and 15) in 15! so there are 3 trailing zeros.

My initial codes:

public static int trailingZeros(int n) {
		int exponent = 1;
		int number = 0;
		while (Math.pow(5.0, exponent * 1.0) <= n) {
			number += n / (int) Math.pow(5.0, exponent * 1.0);
			exponent++;
		}
		return number;
	}

Solution:

	public static int numZeros(int num) {
		int count = 0;
		if (num < 0) {
			System.out.println("Factorial is not defined for < 0");
			return 0;

		}
		for (int i = 5; num / i > 0; i *= 5) {
			count += num / i;
		}
		return count;
	}

Comments: Error condition!

Advertisements

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

%d bloggers like this: