15 AnswersNew Answer
15 AnswersNew Answer
I don't know if such algorithm exists, but you can reach O(1) time complexity (sort of...) by using recursion + memoization (dynamic programming). In other words, calculate the factorials recursively while storing them at a dictionary. So whenever you need them again, simply access them from the dictionary, which is an O(1) operation. See my code snippet: https://code.sololearn.com/cSWq4LUuh0fd/?ref=app
Anna time complexity is probably immaterial for such a small range of 1 to 100 or even 1 to 1000. For larger ranges you probably need to consider the trade off between memory (of the dictionary) and time performance.
Oma Falk what do you mean, lol?
VcC could you explain your comment or point to a link?
n! = (2k+1)! = 1*2*...*(k-2)*(k-1)*k*(k+1)*(k+2)*...*2k*(2k+1) = k * ((k-1)*(k+1)) * ((k-2)*(k+2))*...*(1*(2k+1)) = k * (k² - 1²) * (k² - 2²) * (k² -3²) * ... * (k² - (k-1)²) for odds
Kishalaya Saha f4 here https://code.sololearn.com/c3A818bmOSGM/?ref=app
The function fact(n) itself has a time complexity of O(1). I don't think it's possible without this kind of cheating. https://code.sololearn.com/cnHlSF13axhB/?ref=app
check for zero
How about extracting all the 2's from factorial? For example, factorial(12) = 2^10 * (1) * (1 * 3) * (1 * 3 * 5) * (1 * 3 * 5 * 7 * 9 * 11) Each term in parentheses can be used to help find the next term. They are the products of odd numbers up to 12/2^k for k = 3, 2, 1, 0.
The problem with factorial is that the bigger your number the more complex the multiplication. So fact(n) done naively has a n2logn complexity. Using better algorithms you can reach nlogn^3loglogn
See here : the first method is better for large n because divide and conquers reduces the number of huge number multiplications https://code.sololearn.com/c3A818bmOSGM/?ref=app
works only for numbers up to 12, but is a purely mathematical solution https://code.sololearn.com/c49Q17Nx2jsV/?ref=app
This code, which I don't understand yet, is faster than math.factorial!!! https://code.sololearn.com/coJdFXmoQRex/?ref=app Well, for large numbers (bigger than 1000). For small numbers it's hard to beat library functions, which are probably written in C. More details: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm This page is pretty much a repository of all factorial algorithms.
Sololearn Inc.4 Embarcadero Center, Suite 1455
Send us a message