Welcome everyone with another problem to solve! Today we have some nice math to work with: factorials! We are going to build an algorithm to : we’ll see how fast they grow and how big they get, and finally, we will calculate the sum of their digits to solve our problem. calculate huge factorials Today’s problems are given by : a super cool website to look at if you are in the mood for some head-scratching! There are more than 800 math and coding problems to solve and a vast archive of discussions about them. It is literally the perfect tool to train your math skills and learn something new. Go check it out and try to solve your challenges too! ProjectEuler.net Enough talking: let’s see what today’s problem has to offer. n! means n * (n-1) * … * 3 * 2 * 1. For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800, and the sum of the digits of 10! is 3+6+2+8+8+0+0 = 27. Find the sum of the digits in the number 100! As we anticipated before, what we are asked to do is to , in particular, the number 100! = 100 * 99 * … * 3 * 2 * 1 : pretty easy...right? Well, not quite! calculate the digits of a number Let’s put down some basics then and see how to manage such a big product. Factorials! The particular notation stated by the problem is a famous concept in math known as . The factorial of a number is simply . It’s usually expressed with the expression mark after the number (n!) or, in symbols, as factorial the product of all the natural numbers up until that number So, for instance, the factorial of the number 10, written as 10!, is 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800. What’s really cool about factorials is since we are used to dealing with Big-O complexity notation, here’s a chart comparing some function’s growth rates. It’s pretty clear that the factorial growth is the : for an , the number of operations executed by a factorial growing function exceeds (by a lot) a thousand operations! how fast they grow: worst instance size of less than 10 One simple way to see this behavior is to : if you still have your scientific calculator from high school, like the famous Casio or Sharpe, you can easily see that : it gives you back a math error. This is because the number cannot be stored by the memory of the calculator, for it gets . try with a calculator you can’t calculate over 69! too big to address Some more recent calculators try to go over that bond: for example, the calculator of my phone (a Redmi 7) can calculate up to 170!, giving out the result with the exponential notation (7.25741562e³⁰⁶) if you try with 171! though, it just spits a disappointing ∞ … which is really not the case. It’s also really cool to look at how many digits the result of a factorial has: the number 100! has 158 digits the number 500! has 1135 digits the number 1000! has 2568 digits the number 5000! has 16326 digits The number 10000! has 35660 digits: it is so big that I could not fit it in a single image. Here’s a GIF with all the digits: But wait a minute: didn’t we just say that we could not calculate over the factorial of 70? There’s a trick to do so that we’ll see in a moment. But to understand how we can calculate arbitrarily big factorials, we first must go back to the basics of multiplication. How we multiply When you were kids, chances are that your teacher at school taught you to multiply in columns with a process similar to this: On the left side, a simple multiplication between a three-digit number and a one-digit number, in which each digit from the right to the left gets multiplied by 9. At each multiplication, if the result is greater than 9, the remainder is written on top of the next digit (right to left) and added on the next step of the process; on the right side, a multiplication of a three-digit number and a two-digit number, where there are two “temporary” results in between of the process. Here, we previously wrote a 0 as the rightmost digit in the second temporary result and summed those to get the final result. It’s really basic math, but this process works because we can the starting number in units, tens, hundreds, and so on, and multiply each of those by the second number. After that, we just sum each individual partial result to obtain the final result. Something like this: decompose That is precisely what we are going to do on a much bigger scale. We are going to deal with very big numbers, so this process needs to be modified a bit to work with the integer’s memory limits built into the language we are using (Python, in this case). To be true, Python 2 used to have a size limit in it’s type, but since Python 3 replaced it, the limit was somehow removed. Other languages do have it, though, so we build this approach to keep the algorithm portable to those languages too. Also, it will come in handy to multiply from the right to the left. int Coding the process Basically, we first convert our number to a string and reverse it. After that, we multiply each digit for the second number, add the previous remainder, and store the result and the new remainder for the next calculation. Let’s see the process step by step first: With this process, ideally, the only two limits we have on our products are: : when the number we are trying to multiply gets too big, we’ll be thrown a , for the interpreter has not enough memory to allocate the calculated number. Every modern computer has 8, 16, or 32Gb of RAM tough, so you should have plenty of memory to allocate before reaching the limit. The RAM limit MemoryError as we’ll see better later, the time needed to complete the process grows pretty quickly. Even if it’s not a real limit (one can always wait, right?), the more the number grows, the more time you’ll need to wait for a result. The time limit: Our code will replicate this process step by step, returning the result. Here’s the code: https://gist.github.com/NicolaM94/5d81f8696c340adc80fcbbff6c957e2d?embedable=true The function accepts two arguments: , the number to multiply as string, and , the other one as integer. First off, we reverse and create two other variables: multiplication n m n , which will hold our new number digit by digit newNumber , which will keep track of the remainder of each operation. The remainder is initially equal to 0. remainder We loop over the reversed number and, at each step: We calculate the of the digit, we are on times the second number and add the remainder. result m We add the last digit of to the ; result newNumber If there is a remainder (when ), we update the variable with the new one. The remainder is composed by the digits of except the last one. If there is no remainder, we set back to 0. result > 9 remainder result remainder This is really important to avoid bringing on remainders of previous multiplications! We keep looping for each digit of and finally, if there is a remainder after the last multiplication, we add it to . After that, we simply return our . reversed newNumber newNumber Calculating the factorial Now that we have a method to multiply numbers of the size we want, we can apply it to calculate our factorials! Here’s the code: https://gist.github.com/NicolaM94/95fee9b37cba1078ec40a100ed525de5?embedable=true It’s just a really: all it does is set a variable , initially equal to the string “1” and then range from 1 to (n+1 really, for Python’s range stops at n-1) to apply our function, each time updating with the new result. wrapper, out n multiplication out For example, here’s the result of 500!: 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 Summing up Since our problem requires us to calculate the sum of the digits of 100!, we also need a function to sum all the digits, but it’s quite simple to build: you can do it directly in your function. Here’s the main: main https://gist.github.com/NicolaM94/46aa1b7cb2d13d2efda3f748c423ae5d?embedable=true#file-factorialcalculator-py As in where the problem was also given by , I won’t give out the solution: you need to build this by yourself, at least, if you want to know it! besides presenting math riddles and problems, . And I love that: they are so committed that publishing results and guides for their problems is actually forbidden (this is one of the first 100 problems, so I understand it is permitted). Given this, . the other article ProjectEuler.net ProjectEuler.net is really a lovely project: their main focus is to provide a tool to start learning, thinking, and reasoning about math I don’t feel it would be fair to just give out the solution to copy-paste and get the achievement Have a nice coding, guys! 😎 Time and complexity It’s not that hard to evaluate the time complexity of this algorithm: the biggest amount of time is spent inside the function. Here, besides allocating some variables and modifying their values, the slowest part is the for loop, which will run times, depending on the length of the number we are multiplying. It is linear, since there are no nested loops to deal with. multiplication len(n) When we wrap this function in though, we must run that function times: so the time complexity becomes quadratic, leaving us with O(n²) t.c. hugeFactorial n Finally, summing up the digits it’s another linear time algorithm, but it’s only invoked after the factorial is calculated: for this reason, it won’t add any complexity, leaving us with a total complexity of . O(n²) Talking about execution time, here’s the time taken by my machine (AMD Ryzen 5, avg. ck. 2700 MHz) to calculate some results: With a simple regression, even if the data is clearly not enough, we can see that our prediction of a O(n²) time complexity holds true: the time taken actually grows like a parabola. I did not have much time to go over 10000!, so if you try it out, please let me know your results! Conclusions Here it is; this was my tackle! In all likelihood, there are better approaches to this kind of problem, but, as always, I wanted to share my try with you guys. What do you think about this? Do you have a better solution or idea? Let me know in the comments! I hope you liked the article and found something interesting in it! If so, please leave a like or share it with someone who could appreciate this kind of problem: that would really make my day! Thanks for reading; as always

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Daily Coding Problem: Computing Big Exponentials

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Daily Coding Problem: Computing Big Exponentials

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps