CODEWITHSUNDEEP
c#mathnumbers
munificent
munificent

Reputation: 133

Number of zeroes at the end of factorial

I need to find the number of zeroes at the end of a factorial number. So here is my code, but it doesn't quite work :/ 

using System;

class Sum
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        long factoriel = 1;

        for (int i = 1; i <= n; i++)
        {
            factoriel *= i;
        }

        Console.WriteLine(factoriel);

        int timesZero = 0;

        while(factoriel % 10 != 0)
        {
            timesZero++;
        }
        Console.WriteLine(timesZero);
    }
}

I know I can use a for loop and divide by 5, but I don't want to. Where is the problem in my code and why isn't it working?

Upvotes: 2

Views: 2473

Answers (5)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186833

There's problem with your algorithm: integer overflow. Imagine, that you are given

  n = 1000

and so n! = 4.0238...e2567; you should not compute n! but count its terms that are in form of (5**p)*m where p and m are some integers:

  5 * m gives you one zero
 25 * m gives you two zeros
625 * m gives you three zeros etc

The simplest code (which is slow on big n) is

  static void Main(string[] args) {
    ...
    int timesZero = 0;
    
    for (int i = 5; i <= n; i += 5) {
      int term = i;
    
      while ((term % 5) == 0) {
        timesZero += 1;
        term /= 5;
      }
    }
    ...
  }

Much faster implementation is

  static void Main(string[] args) {
    ...
    int timesZero = 0;
    
    for (int power5 = 5; power5 <= n; power5 *= 5) 
      timesZero += n / power5;
    
    ...
  }

Upvotes: 5

Pazzo
Pazzo

Reputation: 1

Your code seems fine, just a little correction in the while-condition: 

        public static int CalculateTrailingZeroes(BigInteger bigNum)
    {
        int zeroesCounter = 0;

        while (bigNum % 10 == 0)
        {
            zeroesCounter++;
            bigNum /=10;
        }

        return zeroesCounter;
    }

That works, I just tested it.

Upvotes: 0

Rizwan Joiya
Rizwan Joiya

Reputation: 1

static void Main(string[] args)
        {
            Console.WriteLine("Enter the number:");
            int n = int.Parse(Console.ReadLine());
            int zero = 0;
            long fac=1;
            for (int i = 1; i <= n; i++)
            {
                fac *= i;
            }
            Console.WriteLine("Factorial is:" + fac);
        ab:


        if (fac % 10 == 0)
        {
            fac = fac / 10;
            zero++;
            goto ab;
        }
        else
        {
            Console.WriteLine("Zeros are:" + zero);
        }
        Console.ReadLine();
        }

Upvotes: 0

Jaydeep Shil
Jaydeep Shil

Reputation: 1959

Make sure to add inbuilt Reference System.Numeric

using System.Text;
using System.Threading.Tasks;
using System.Numeric

namespace TrailingZeroFromFact
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter a no");
            int no = int.Parse(Console.ReadLine());
            BigInterger fact = 1;
            if (no > 0)
            {
                for (int i = 1; i <= no; i++)
                {
                    fact = fact * i;
                }
                Console.WriteLine("{0}!={1}", no, fact);
                string str = fact.ToString();
                string[] ss = str.Split('0');
                int count = 0;
                for (int i = ss.Length - 1; i >= 0; i--)
                {
                    if (ss[i] == "")
                        count = count + 1;
                    else
                        break;
                }
                Console.WriteLine("No of trailing zeroes are = {0}", count);
            }
            else
            {
                Console.WriteLine("Can't calculate factorial of negative no");
            }
            Console.ReadKey();
        }
    }
}

Upvotes: 0

Rana Rajput
Rana Rajput

Reputation: 1

Counting Trailing zeros in Factorial

static int countZerosInFactOf(int n)##
{   
    int result = 0;
    int  start = 1;
    while (n >= start)
    {
        start *= 5;
        result += (int)n/start; 
    }
    return result;
}

Upvotes: 0

Related Questions