We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This algorithm works the way we learned how to do multiplication in 3rd grade, but using a super carry as opposed to a one digit carry. So instead of multiplying each digit of the first number by each digit of the second number, we multiply each digit of the first number by the entire second number. This resuls in a "super carry", a carry that could be greater than a two digit number. It took me a long while to get this though - if written in C or a language that doesn't support more than 64 bit multiplication - this question should be marked as hard.
Not really. I did the same approach in c++ and checked how large the "super carry" could get. When calculating 100! it never reaches 100, well in the limits of an int. Anyone curious or doubting can just copy the code above and add a few lines to check.
well pretty much every problem here should be marked lower than currently is if you are using python or in some cases even any OOP language because you are just calling functions of that language that will solve the problem for you...
Thank you for your comment. May I ask a little about your solution ?
My solution is almost exactly the same, excep that in this while loop
while (carry)
{
len++;
int dig = carry % 10;
arr[len - 1] = dig;
carry /= 10;
}
I did not have the step dig = carry % 10, and my answer was correct up to 15 !, but after that it was wrong. It worked for numbers even as big as 25 ! when I added the line dig = carry % 10.
I really don't understand why because I wrote my program in C++ and even store everything in unsigned long, which gives me the maximum of bits I can think of..But yours seem to be written in C and you stored everything in int ? When I tried to store my variables in int, it did not give the correct answer.
I would really appreciate if someone knows the answer why there is such a difference in result !
Thank you
Extra Long Factorials
You are viewing a single comment's thread. Return to all comments →
This algorithm works the way we learned how to do multiplication in 3rd grade, but using a super carry as opposed to a one digit carry. So instead of multiplying each digit of the first number by each digit of the second number, we multiply each digit of the first number by the entire second number. This resuls in a "super carry", a carry that could be greater than a two digit number. It took me a long while to get this though - if written in C or a language that doesn't support more than 64 bit multiplication - this question should be marked as hard.
this naive super carrier added to next result could be so big over int limit, it's not practical in this question.
Not really. I did the same approach in c++ and checked how large the "super carry" could get. When calculating 100! it never reaches 100, well in the limits of an int. Anyone curious or doubting can just copy the code above and add a few lines to check.
Question states: 1<=n<=100 So largest possible multiplication: 9*100 which is well under limit of int
It would be better if you could explain with an example.
Thnks for the super carry explanation!!.......I was stuck in that for quite long before reading discussion..
well pretty much every problem here should be marked lower than currently is if you are using python or in some cases even any OOP language because you are just calling functions of that language that will solve the problem for you...
Thanks for the nice explanation!!
Hi Etayluz,
Thank you for your comment. May I ask a little about your solution ?
My solution is almost exactly the same, excep that in this while loop while (carry) { len++; int dig = carry % 10; arr[len - 1] = dig; carry /= 10; }