CodeChef – Factorial

using System;
					
public class Program
{
	public static void Main()
	{
		int dataSize = int.Parse(Console.ReadLine());
		double[] data = new double[dataSize];
		
		for(int i = 0; i < dataSize; i++)
		{
			data[i] = double.Parse(Console.ReadLine());
		}
		
		for(int i = 0; i < dataSize; i++)
		{
			Console.WriteLine(FindTrailingZeros(data[i]));
		}
	}
	
	public static double FindTrailingZeros(double n)
	{
		double quotient = 1;
		double sumOfQuotients = 0;
		int power = 1;
		
		while(true)
		{
			quotient = n / Math.Pow(5, power);
			quotient = Math.Truncate(quotient);
			power++;
			
			if(quotient > 0)
			{
				sumOfQuotients += quotient;
			}
			else
			{
				return sumOfQuotients;
			}
		}
	}
}

Here’s my code for the Factorial problem on CodeChef, though I think the title doesn’t really describe the problem well. You are not supposed to find the factorial of a number but rather the number of trailing zeros of the factorial. My first instinct was to find the factorial, put the numbers in a string, and iterate through the string to check for zeros. The problem with that algorithm though is that factorials are huge! And moreover, an input could be as large as 1 billion which would produce an astronomically large number. So I read the editorial for the problem and they had a little trick for finding trailing zeros of a factorial which was way more efficient.

Here’s a link to the problem.

Advertisements

One thought on “CodeChef – Factorial

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