Factorial zeros

Optimal solution

The trick here is to consider the contributions in terms of 5-factors from all numbers that contribute once, then twice, then thrice and so on. There will be always enough 2-factors, so we don't have to care about those.



In [1]:

    
countZeros :: Int -> Int
countZeros n
    | n < 5 = 0
    | otherwise = n `div` 5 + countZeros (n `div` 5)

One can try to inject an error in this function, e.g.

| n == 74 = 0

Amazingly, it appears that QuickCheck is able to find it!

Brute force solution



In [2]:

    
countZeros' :: Int -> Int
countZeros' n =
    let n' = toInteger n in
        length $ takeWhile (== '0') $ reverse $ show $ product [1..n']

Testing using QuickCheck

Now, let's test our solution:



In [3]:

    
import Test.QuickCheck



In [4]:

    
testCountZeros :: Int -> Bool
testCountZeros n = countZeros n == countZeros' n



In [5]:

    
quickCheck testCountZeros









    





+++ OK, passed 100 tests.

Note that we have to convert n to Integer (bignum) in the brute-force version (countZeros'). This is because the type of product is defined as follows:

product :: Num a => [a] -> a

Consequently, if you call product on an Int, it will operate with Ints (and suffer from possible overflows), but if you call it on an Integer, it will operate with Integers, which can hold arbitrary large integer numbers. Thus, if one fails to use the bignums to compute the factorial using product, QuickCheck finds a problematic test case in no time:

*** Failed! Falsifiable (after 25 tests): 
21

In order to fix the problem, one either has to switch to Integer everywhere and then use fromIntegral on the result of length, which for obvious reasons is defined as length :: [a] -> Int, or else (my preferred solution) keep using Int everywhere, but switch to bignums for the product.



In [6]:

    
product [1..(21 :: Int)]
product [1..(21 :: Integer)]









    





-4249290049419214848






    





51090942171709440000