Hackerrank Solution: Manasa and Factorials

Original Problem

Manasa was sulking her way through a boring class when suddenly her teacher singled her out and asked her a question. He gave her a number n and Manasa has to come up with the smallest number m which contains atleast n number of zeros at the end of m!. Help Manasa come out of the sticky situation.

Input Format 
The first line contains an integer T i.e. the number of Test cases. 
Next T lines will contain an integer n.

Output Format 
Print smallest such number m.

Constraints 
1 ≤ T ≤ 100 
1 ≤ n ≤ 10¹⁶

Sample Input

3
1
2
3

Sample Output

5
10
15

Explanation

1. As 4! = 24 and 5! = 120, so minimum value of m will be 5.
2. As 9! = 362880 and 10! = 3628800, so minimum value of m will be 10.
3. As 14! = 87178291200 and 15! = 1307674368000, so minimum value of m will be 15.

Solution

We are looking for the smallest \(m\) such that \(m!\equiv 0\pmod{10^n}\). Since the number of fives as a prime factor of 10 in \(10^n\) is equivalent to the number in \(5^n\), we can equivalently write \(m!\equiv 0\pmod{5^n}\). That means there exists a number \(r\) for the rest such that \(m! = r \cdot 5^n\). To come up with a reasonable upper bound, we ignore \(r\) and say \(m! \leq 10^{10^{16}}\) and solve for \(m\) by taking the \(\log({m!}) \leq 10^{16}\Leftrightarrow\sum\limits_{i=1}^m\log{i}\leq 10^{16}\) from which the upper bound \(m_u=694100859679691\) follows. This upper bound is not enough, since it covers only the number of trailing zeros, so guessing the real upper bound to be 100 times larger than the calculated one sounds okay. Since the number of zeros grows with \(m\), we can now do a binary search or even better an interpolation search on a function that counts the trailig zeros by canceling out \(5, 25, 125, ...\) as derived before and the large upper bound doesn't harm that much anymore. Hence \(\#_0(m) = \sum_{i=1}^{\infty} \left\lfloor\frac{m}{5^i}\right\rfloor\) can be implemented as

def countTrailingZeros(m)
  s = 0
  p = 5
  while p <= m
    s+= m / p
    p*= 5
  end
  return s
end

Or stated recursively:

def countTrailingZeros(m)
  return 0 if m == 0
  return m / 5 + countTrailingZeros(m / 5)
end

Implementing a binary search can then look as follows (yes, we could use ruby's bsearch method, too):

gets.to_i.times {
  n = gets.to_i
  r = -1
  l = 0
  u = 69410085967969100
  while l <= u
    m = (l + u) / 2

    if n <= countTrailingZeros(m)
      r = m
      u = m - 1
    else
      l = m + 1
    end
  end
  puts r
}