CODEWITHSUNDEEP
c#algorithm
roughblot
roughblot

Reputation: 100

FCTRL - Factorial on SPOJ

Can anyone help me with what mistake am I making ? This is just a simple problem to calculate trailing zeroes for number's factorial.

The output works successully on Ideone, but for some reason throws

"Wrong answer"

on SPOJ's compiler.

Can someone please spot the mistake that I'm making.

https://ideone.com/BTVOfu

using System;

public class Test
{
    public static void Main(string[] args)
    {
        int numberOfValues = int.Parse(Console.ReadLine());
        int[] values = new int[numberOfValues];

        for(int i=0;i<numberOfValues;i++)
        {
            values[i] = int.Parse(Console.ReadLine());
        }

        for (int i = 0; i < numberOfValues; i++)
        {
            Console.WriteLine(calculateFact(values[i]));
        }

        Console.ReadKey();
    }

    static int calculateFact(int value)
    {
        int finalValue = 0;
        for (int i = 0; value > 5; i++)
        {
            value = value / 5;
            finalValue += value;
        }

        return finalValue;
    }
}

Upvotes: 2

Views: 339

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186803

It's very time to implement and run some tests to find out "wrong answer"s:

using System.Linq;
using System.Numerics;

...

// Slow, ugly but easy to understand and check routine
static int naiveCount(int value) {
  BigInteger factorial = 1;

  for (int i = 1; i <= value; ++i)
    factorial *= i;

  return factorial.ToString().Length - factorial.ToString().TrimEnd('0').Length;
}

...

var counterExamples = Enumerable
  .Range(0, 100)
  .Select(v => new {
     value = v,
     actual = calculateFact(v),
     expected = naiveCount(v), })
  .Where(item => item.expected != item.actual)
  .Select(item => $"value: {item.value,4} actual: {item.actual,3} expected: {item.expected,3}");

Console.Write(string.Join(Environment.NewLine, counterExamples));

Outcome:

value:    5 actual:   0 expected:   1
value:   25 actual:   5 expected:   6
value:   26 actual:   5 expected:   6
value:   27 actual:   5 expected:   6
value:   28 actual:   5 expected:   6
value:   29 actual:   5 expected:   6

When having counter examples, it's easy to debug for instance calculateFact(5) case. Can you see the problem now? It's in the for loop: 

for (int i = 0; value > 5; i++)

which should be (>= instead of >)

for (int i = 0; value >= 5; i++)

Edit: Technically, all you have to do is to check powers of 5:

static int calculateFact(int value) {
  int result = 0;

  // 13 loops = floor(log(2**31)/log(5))
  for (int power5 = 5; power5 <= int.MaxValue / 5; power5 *= 5) 
    result += value / power5;

  return result;
}

Upvotes: 3

xanatos
xanatos

Reputation: 111890

You probably get an out-of-memory error. You don't need an int[] values. You can calculate the factorial immediately after reading a number. And you don't need the Console.ReadKey();. Note that I haven't checked the correctness of calculateFact.

And as noted by Dmitry, your function is wrong... You are "off by one":

for (int i = 0; value >= 5; i++)

See the >=? But you can speed it up a little by removing the i variable.

static int calculateFact(int value)
{
    int finalValue = 0;

    while (true)
    {
        value /= 5;

        if (value == 0)
        {
            return finalValue;
        }

        finalValue += value;
    }
}

This should be correct, but I'm not sure it is fast enough (often SPOJ problems are based on "caching" data)

Upvotes: 1

Related Questions