Computing small factorials | Don't be just cut-n-pasters

Computing small factorials

March 7, 2009 at 1:50 pm narinderberi 1 comment

This one is good for quick brush up of programming skills:

http://www.codechef.com/problems/FCTRL2/

Entry filed under: Uncategorized.

Number of zeros in a Factorial Compute path distance

1 Comment Add your own

1. Narinder Beri | March 7, 2009 at 1:52 pm

I simply used a linked list (in C) or a dynamic vector (in Perl, C++) to program the logic of multiplying huge numbers. This is the code:

#

use strict;

main();

sub main
{
my $numcases = ;
chomp($numcases);

my @list = ();

for(my $i = 0; $i < $numcases; $i++)
{
my $num = ;
chomp($num);

push @list, $num;
}

for(my $i = 0; $i <= $#list; $i++)
{
my $num = $list[$i];

my $factStr = factorial($num);

print $factStr, “\n”;
}
}

sub factorial
{
my $num = $_[0];

my @fact = (1);

for(my $i = 1; $i <= $num; $i++)
{
my $carry = 0;

for(my $j = 0; $j = 100000)
{
my $rem = $factComp % 100000;

$carry = ($factComp – $rem) / 100000;

$factComp = $rem;
}
else
{
$carry = 0;
}

$fact[$j] = $factComp;
}

if($carry > 0)
{
if($carry >= 100000)
{
die “Problem”;
}

push @fact, $carry;
}
}

my $factStr = stringify(@fact);

return $factStr;
}

sub stringify
{
my @fact = @_;

my $factStr = “”;

for(my $i = $#fact; $i >= 0; $i–)
{
my $factComp = $fact[$i];

my $str = “”;

if($i == $#fact)
{
$str = sprintf(“%d”, $factComp);
}
else
{
$str = sprintf(“%05d”, $factComp);
}

$factStr .= $str;
}

return $factStr;
}

Leave a comment

Trackback this post | Subscribe to the comments via RSS Feed