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?)