COME ON CODE ON

A blog about programming and more programming.

Factorial

with 6 comments

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,  4! = 1 x 2 x 3 x 4 = 24

In programming, factorial comes to use at many places. Sometimes you simply have to calculate factorials but in C/C++ you are limited by the range of integers. Even long long can store only up-to 20! . 

int main()
{
    long long i,j=1;
    for (i=1;i<21;i++)
    {
        j*=i;
        printf("%lld! = %lld\n",i,j);
    }
}&#91;/sourcecode&#93;

So you have to find factorials using strings and multiply the way you used to do in std I or II. If you haven't done so do now, you will learn a lot. Or if you know some language like Python or Haskell, which allow larger numbers you need not worry. For example,  a code to accept t number of test cases and then print the factorial of next t numbers(less than 100) in python would be :

&#91;sourcecode language='python'&#93;

f=&#91;1&#93;*101
for i in range(2,101):
    f&#91;i&#93;=f&#91;i-1&#93;*i

n=input()
for i in range(0,n):
    x=input()
    print f&#91;x&#93;&#91;/sourcecode&#93;

Sometimes the question can be to find n! as a power of primes. To know the power of prime in a factorial you can use the formula:
<em>                  ε</em><sub>p</sub> = ⌊n/p⌋ + ⌊n/<em>p</em><sup>2</sup>⌋ + ⌊n/<em>p</em><sup>3</sup>⌋...

where <em>ε</em><sub>p</sub> is the power of prime p in factorial n.

<strong>Number of trailing zeroes in n Factorial</strong>

Finding number of trailing zeroes is very easy. Because you can get a zero only through a multiple of 5. So the number of trailing zeroes is equal to the multiples of five which is :
<em>                         ε</em><sub>5</sub> = ⌊n/5⌋ + ⌊n/<em>5</em><sup>2</sup>⌋ + ⌊n/<em>5</em><sup>3</sup>⌋...

A simple c-sharp program to get t test cases and then output the number of trailing zeroes in the factorial of next t numbers would be :

using System;
 

class Program
{
    public static void Main()
    {
        int T, N, sum, x;
        T = int.Parse(Console.ReadLine());
        while (T>0)
        {
            N = int.Parse(Console.ReadLine());
            x = 5;
            sum = 0;
            while (N / x > 0)
            {
                sum += N / x;
                x *= 5;
            }
            Console.WriteLine(sum);
            T--;
        }
    }
}

I will be writing soon on how to find the last non-zero digit and if possible also last k non zero digits.

ciao
fR0D

Advertisements

Written by fR0DDY

June 20, 2009 at 12:39 PM

Posted in Programming

Tagged with , , , , , , , , ,

6 Responses

Subscribe to comments with RSS.

  1. An interesting way to calculate a factorial is to compute them at compilation time rather than computing them at runtime using C++ template metaprogramming.

    Code taken from wikipedia:

    template <int N>
    struct Factorial 
    {
        enum { value = N * Factorial<N - 1>::value };
    };
     
    template <>
    struct Factorial<0> 
    {
        enum { value = 1 };
    };
     
    // Factorial<4>::value == 24
    // Factorial<0>::value == 1
    void foo()
    {
        int x = Factorial<4>::value; // == 24
        int y = Factorial<0>::value; // == 1
    }

    dominiko

    June 20, 2009 at 3:28 PM

  2. Hey, thanks dominiko, for pointing me to that!

    fR0D

    June 20, 2009 at 3:33 PM

  3. […] COME ON CODE ON A blog about programming and more programming. « Factorial […]

  4. Hey,
    I assume u are using SyntaxHighlighter plugin in wordpress to display these code snippets. Can u tell me how u r doing it? Do we need to have a wordpress.org account to be able to use that plugin?
    Also, i see that u are using LateX too? What plugin is used for that?

    Thanks!

    aj

    October 26, 2009 at 3:44 AM

  5. Thanks a lot!

    ajaygopalakrishnan

    October 26, 2009 at 9:03 AM


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: