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.
int main(){
int n;
scanf("%d",&n);
int arr[1000] = {0};
arr[0] = 1;
int len = 1;
for (int i = 2; i <= n; i++) {
int carry = 0;
for (int j = 0; j < len; j++) {
int mul = i * arr[j] + carry;
int dig = mul % 10;
arr[j] = dig;
carry = mul / 10;
}
while (carry) {
len++;
int dig = carry % 10;
arr[len - 1] = dig;
carry /= 10;
}
}
for (int i = len - 1; i >= 0; i--) {
printf("%d", arr[i]);
}
return 0;
}
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
Fantastic. I got an idea, what u are doing. But the code bieng so simple and small. I amamazed at how you reach the solution. I could not decipher the code yet. I understood you were doing like we used to multply using paper and pencils. Kudos. All the best for your career.
defget_factorial2(n):old=[1]current=[]foriinxrange(2,n+1):carry=0fordigitinold:prod=int(digit)*i+carryrem=prod%10current.append(rem)carry=prod/10ifcarry!=0:forjinstr(carry)[::-1]:current.append(j)# add j as a strold=currentcurrent=[]return"".join(map(str,old[::-1]))# convert everything to str before concatenation and returning the resultsn=int(raw_input().strip())printget_factorial2(n)
Here my python solution using super carry method. Exactly same as @etayluz's
logic : -
suppose you're asked to multiply 25 with 24..
what toddlers do..
25
* 24
100
50 *
600
what we do...
5*24=120, 0 stays, carry 12... then 2*24+12=60.. hence 600.
this method is called supercarry.
Take an array, use this supercarry method and for every i, print a digit in array[i]. then print the anti-array.
If there are extra zeroes in front of the answer, remove them by using..
for (i = len; i >= 0; i--)
if (a[i] != 0) {
neww = i;
break;
}
for (i = neww; i >= 0; i--)
printf("%d", a[i]);
Can you explain how i <= len + 1 is working correctly? When I try to multiply two numbers (1050 * 1049) using your code, it's producing wrong results, it's missing some digits.
Extra Long Factorials
You are viewing a single comment's thread. Return to all comments →
why don't you just do it in c or c++ ? you have to implement big integers by your ownself....
Is there any datatype to store such huge numbers!!!!OMG!!!!!!!!!!!!!!!!!!!!!
i did it by storing the factorial value digits in an array....and it simply works!!!!(no tension of data type limits....) :)
Ty!!That helped:)
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; }
Thanks for help!
Fantastic. I got an idea, what u are doing. But the code bieng so simple and small. I amamazed at how you reach the solution. I could not decipher the code yet. I understood you were doing like we used to multply using paper and pencils. Kudos. All the best for your career.
very good work. impressive...
Wow!
Here my python solution using super carry method. Exactly same as @etayluz's
nice way to solve this one
thank you for your help sir,because of you i got this code
Very nice logic. I learned something new. Thank you Sir.
Thanks for the approach.
@etayluz Thank you so much for the explanation!
i cant even think of solving it in c,its really invloves deep thinking to solve it.thats great of u....
how
How??
CAN U EXPLAIN THIS ???
BigInteger in java
YES in java we have BigInteger
solution of this code in c...
logic : - suppose you're asked to multiply 25 with 24..
what toddlers do..
* 24
100
50 *
600
what we do... 5*24=120, 0 stays, carry 12... then 2*24+12=60.. hence 600. this method is called supercarry. Take an array, use this supercarry method and for every i, print a digit in array[i]. then print the anti-array. If there are extra zeroes in front of the answer, remove them by using..
for (i = len; i >= 0; i--) if (a[i] != 0) { neww = i; break; } for (i = neww; i >= 0; i--) printf("%d", a[i]);how your multiplication goes..
n=25.
52 006 00831 006303
etc..
when you print the anti-array
the number prints without any problem...
Can you explain how i <= len + 1 is working correctly? When I try to multiply two numbers (1050 * 1049) using your code, it's producing wrong results, it's missing some digits.
But Factorial is working fine. Can you explain?