#include "stdafx.h"
#include "Fact.h"

#include <climits>
#include <fstream>
#include <iostream>

std::ifstream in("fact.in");
std::ofstream out("fact.out");

int main()
{
    Fact f = Fact();
    long long p = 0;

    in >> p;

    out << f.GetMaxFactorialWithPTrailingZeroes(p);
}

Fact::Fact()
{
}

void Fact::Test()
{
    // Test ExtractPowersOf
    auto result = ExtractPowersOf(0,2);
    result = ExtractPowersOf(10,2);
    result = ExtractPowersOf(8,2);
    result = ExtractPowersOf(1024,2);
    result = ExtractPowersOf(1024,5);
    result = ExtractPowersOf(7,5);
    result = ExtractPowersOf(25,5);
    result = ExtractPowersOf(1000,5);
    result = ExtractPowersOf(3232000,2);
    result = ExtractPowersOf(3232000,5);

    // Test GetMaxFactorialWithPTrailingZeroes
    result = GetMaxFactorialWithPTrailingZeroes(0);
    result = GetMaxFactorialWithPTrailingZeroes(1);
    result = GetMaxFactorialWithPTrailingZeroes(2);
    result = GetMaxFactorialWithPTrailingZeroes(5);
    result = GetMaxFactorialWithPTrailingZeroes(10);
    result = GetMaxFactorialWithPTrailingZeroes(1000000);
    result = GetMaxFactorialWithPTrailingZeroes(66);
}

// -1 if nothing exists
// otherwise, the actual number
int Fact::GetMaxFactorialWithPTrailingZeroes(long long p)
{
    // The main strategy is we count a zero as 2*5
    // so we need to count until we have p 2s and p 5s
    unsigned int numberOfTwos = 0;
    unsigned int numberOfFives = 0;
    for (int factorial = 0; factorial < INT_MAX; factorial++)
    {
        numberOfTwos += ExtractPowersOf(factorial, 2);
        numberOfFives += ExtractPowersOf(factorial, 5);

        // Check if we're done
        if (numberOfTwos >= p && numberOfFives >= p)
        {
            return factorial;
        }
    }
    return -1;
}

unsigned int Fact::ExtractPowersOf(int number, int power)
{
    // Divide my this number repeatedly until no more divisions possible
    unsigned int count = 0;
    while(number % power == 0 && number > 0) 
    {
        count++;
        number /= power;
    }
    return count;
}