Last five non-zero digits of a factorial in base b

Question

This HackerRank problem (based on Project Euler problem 160) says:

For any \$n\$, let \$f_b(n)\$ be the last five digits before the trailing zeroes in \$n!\$ written in base \$b\$.

For example,

\$9! = 362880\$ so \$f_{10}(9)=36288\$
\$10! = 3628800\$ so \$f_{10}(10)=36288\$
\$20! = 2432902008176640000\$ so \$f_{10}(20)=17664\$

Input format

First line of each file contains two numbers: \$b\$ (base) and \$q\$ (number of queries). \$q\$ lines follow, each with an integer \$n\$ written in base \$b\$.

Constraints

\$2 \le b \le 36\$
\$1 \le q \le 10^5\$
\$0 \le n \le 10^{18}\$
Every character in \$n\$ is a valid digit in base \$b\$ (0-9, A-Z for values \$>9\$)

Output Format

Output \$q\$ lines. On each line print exactly 5 digits in base \$b\$ - the answer to the \$i\$-th query. If for some \$n\$, \$n!\$ contains fewer than 5 digits, put the corresponding number of leading zeroes before the answer.

I believe the code works:

def treeFactor(low, high):
    if low + 1 < high:
        mid = (high+low) // 2
        return treeFactor(low, mid) * treeFactor(mid + 1, high)
    if low == high:
        return low
    return low * high

def convert(num,b,numerals="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    return ((num == 0) and numerals[0]) or (convert(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

def removeZ(ans):
    while ans[-1] == "0":
        ans = ans[:-1]
    return ans[-5:]

b, q = raw_input().split(" ")
b = int(b)
q = int(q)

for _ in xrange(q):
    ans = int(str(raw_input()), 10)
    if ans < 2:
        print "1"
    else:
        ans = treeFactor(1, ans)
        ans = convert(ans, b)
        ans = removeZ(ans)
        k = len(ans)
        if k < 5:
            ans = (5 - k * "0").join(ans) 
        print ans

However, it doesn't run fast enough to pass the tests. I changed the factorial method and tried to cut down on str() conversions, using xrange() and so on, but it still isn't efficient enough. Can you see any bottlenecks, or methods that could be improved further (without the use of specialist packages like NumPy).

(on a slight side note, would it be possible to perform the factorial method on numbers without converting them to base 10, while maintaining efficiency?)

Answer 1

Note that the constraint in this problem is \$n \leq 10^{18}\$. In other words, the factorials you are calculating can be as large as \$10^{18}!\approx 10^{1.7\cdot 10^{18}}\$. In other words, if you aren't running into a time limit, you will most likely run into a memory limit.

Your function treeFactor calculates:

• \$10000!\$ in 0.06 seconds
• \$100000!\$ in 2.57 seconds
• \$200000!\$ in 9.34 seconds
• \$400000!\$ in 29.73 seconds
• \$1000000!\$ in 129.58 seconds

In other words, even \$1000000!\$ can't be calculated within the time limit. Futher, \$(10^7)!\$ will probably take at least an hour, \$(10^8)!\$ will probably take several days. Even with a lot of optimizations to calculating factorials, it isn't going to make it, unfortunately. Further, I can't think of a faster method now (I tried a few things, but I got recursion limit exceeded).

For this problem, you only need the last five non-zero digits. For this, you'll need to do a few things with modular arithmetic. Only read the text under the spoiler if you want more hints.

For example, create an array with the five last non-zero digits. Take away all factors that cause a factor of the base \$b\$. Also, note that multiplying by a number larger than \$10^5\$ is the same as multiplying by the same number modulo \$10^5\$.

I will not write the solution for you. This problem is quite hard - considering that only four people solved it out of over a hundred attempts. I do not know whether this solution is fast enough (also because there is no time limit specified, and because I didn't code it), but it should at least run within a couple of minutes, if you optimalize enough. The calculation of \$10^{18}!\$ can't be done with any method in any reasonable time.

Answer 2

1. Bugs

1. The code says:

   if ans < 2:
       print "1"
   

   but this is wrong: the output must have exactly five digits. This needs to be:

       print("00001")
   

2. The problem description says that each input \$n\$ is given in base \$b\$. But the code in the post says:

   ans = int(str(raw_input()), 10)
   

   In other words, it always treats the input as a number in base 10. You need to write:

   ans = int(str(raw_input()), b)
   

3. The logic for adding leading zeros is broken:

   if k < 5:
       ans = (5 - k * "0").join(ans) 
   

   This will raise an error:

   TypeError: unsupported operand type(s) for -: 'int' and 'str'
   

   Instead, use the format function:

   ans = format(ans, '>05')
   

2. Review

1. There are no docstrings. What do these functions do? How do I call them? What do they return? It is very hard to check that code is correct until there is some explanation of what it is supposed to do.

2. Python has a built-in function math.factorial. This is a little bit faster than treeFactor, so you might as well use it instead of writing your own:

   >>> from math import factorial
   >>> from timeit import timeit
   >>> timeit(lambda:treeFactor(1, 100000), number=1)
   0.5560502449998239
   >>> timeit(lambda:factorial(100000), number=1)
   0.36733978200027195
   

3. Once you have replaced treeFactor with math.factorial, there is no longer any need for the special case n == 1, so that can be removed.

4. Instead of stripping the trailing zeros one at a time, use the str.rstrip method:

   ans = ans.rstrip('0')
   

5. The code is hard to test because there is code running at top level. For example, suppose I want to check that the code in the post correctly computes \$f_{10}(20) = 17664\$, how would I do it? I have to prepare an input file with appropriate values for \$b\$ and \$q\$ and so on, and then feed this into the program.

   But if the code were organized into functions like this:

   def f(b, n):
       """Return string containing the last 5 non-zero digits of n! in base b."""
       ans = factorial(n)
       ans = convert(ans, b)
       ans = ans.rstrip('0')
       ans = format(ans, '>05')
       return ans
   

   Then I could test it easily:

   >>> f(10, 20)
   '17664'
   

3. Performance

As wythagoras says, this method is never going to work because you can't compute \$10^{18}!\$ (you don't have enough memory to store the result).

You're quite a long way from the answer, so I don't want to spoil the problem for you by writing a solution. Instead, I'll give an easier problem which is an initial step on the road to solving this one:

How many trailing zeros are there in \$n!\$ (in base 10)? For example, \$10! = 3628800\$ and it has 2 trailing zeros. Is there a way to compute this without having to actually compute the factorial? For example, \$10^{10}!\$ has 2499999997 trailing zeros. How did I compute this?

Answer 3

This is not a full answer, but it should be a start (specifically, I will only consider base 10, and not complete the problem, but get you on the right track).

Since n is large, you do not have enough time to compute n! at all. That said, I will start with a way of computing n! that is useful for solving this problem.

1. find all prime numbers from 1 to n
2. realize that p is in n! n//p+n//(p^2)...n/p^(log(n)/log(p)) times. (this is true because n//p numbers have p as a factor once ...)
3. now we have 2 lists, each prime factor in n!, and how often it appears. If we take the product of factor^times, this will be n!.

This is good, but we can improve on it a bunch. for example:

Each 5 we have creates a 0 trailing 0. Instead of making them, and striping them away, we can subtract the number of 5's from the number of 2's, and set the number of 5's to 0.

Furthermore, since we only care about the last 5 digits, if we only use the last five digits of our powers, and take our answer mod 10**5 each time we multiply, we will always be performing integer multiplication which is much faster.

My code is below: with it, this can compute n=100000 in .03 seconds, and n=1000000000 in 11.5 seconds. (still a long way to go, but an 83x speedup)

import numpy as np
from math import log
def prime_range(a=1,n=1000):
    """ Return a list of the primes between a and n. """
    prime = np.ones(n//3 + (n%6==2), dtype=np.bool)
    for i in range(3, int(n**.5) + 1, 3):
        if prime[i // 3]:
            p = (i + 1) | 1
            prime[p*p//3 :: 2*p] = False
            prime[p*(p - 2*(i&1) + 4)//3 :: 2*p] = False
    result = (3 * prime.nonzero()[0] + 1) | 1
    result[0] = 3
    i=0
    while result[i] < a:
        i += 1
    return np.r_[2, result[i:]]

def fact_sin_0s(n):
    primes = prime_range(n=n+1)
    prime_count = n // primes
    for j in range(len(primes)):
        for i in range(2,int(log(n,primes[j]))+1):
            prime_count[j] += n // (primes[j]**i)
    prime_count[0] -= prime_count[2]
    prime_count[2] = 0

    ans = 1
    #print(prime_count)
    for p1, p2 in zip(primes,prime_count):
        ans = (ans * pow(int(p1),int(p2), base**5)) % (base**5)
    return ans

n = 100000
base = 10