CODEWITHSUNDEEP
c++algorithmoptimization
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

C++: Counting zeros at the end optimization

I am trying to solve standard problem of calculating 0s at the end of factorial of any natural number. My code works fine but online judge gives "Time Limit Exceeded" error. Decided to ask here about how I can optimize my code.

#include <iostream>

using namespace std;


int count (int n)
{
    int result = 0;
    for (unsigned int i = 5; i <= n; i += 5)
    {
        int temp = i;
        while (!(temp % 5))
        {
            ++result;
            temp /= 5;
        }
    }
    return result;
}



int main()
{
    int N;
    cin >> N;
    cin.get();
    for (unsigned int i = 0; i < N; ++i)
    {
        int n;
        cin >> n;
        cin.get();
        cout << count (n) << endl;
    }
    return 0;
}

Thanks in advance.

Upvotes: 2

Views: 159

Answers (2)

MBo
MBo

Reputation: 80287

You haven't to check every number divisible by 5. Instead you can count 5's with simple series:

count =  n div 5 + n div 25 + n div 125...

Upvotes: 1

Henrik
Henrik

Reputation: 23324

Try this:

int count (int n)
{
    int result = 0;
    for (unsigned int i = 5; i <= n; i *= 5)
        result += n / i;
    return result;
}

In 1*2*..*N, there are N/5 factors, which are divisable by 5. N/25 of those are also divisable by 25, ...

Upvotes: 2

Related Questions