Ouch!! My eyes are hurtingđ
Since bruteforce algorithm calculate factorial of n. And N is as large as 10^ 5 the factorial of this number canât even be stored in a 64 bit data type. at n = 14 it already exceeds the int range.
Then second point is integer overflow is an undefined behavior so thatâs the reason itâs WA.
I donât think thereâs an analytical approach; that is, youâll probably have to explicitly generate n! as a string.
Letâs see how you would do that. Karatsuba multiplication allows you to multiply two n-digit numbers in O(n^{1.58})-ish time. The intuition is that you donât want to multiply a huge number by a small one, thatâd be a waste of time. So letâs use a divide-and-conquer algorithm (there are way better ways to partition numbers, though) to compute the values of x! and \frac{n!}{x!} efficiently for some x. Itâs generally optimal to pick the x that will even out the values of the two sides, but of course, you canât find it explicitly without actually doing multiplication, so you can use the length of numbers as a heuristic and binary search.
Whatâs the complexity? We have T(n) = 2T(n / 2) + n^{1.58}, which by the master theorem is in fact just O(n^{1.58}). This will probably end up timing out
Maybe you can use other multiplication algorithms with better asymptotics, but most of them seem to have terrible constant factors.
It would be very helpful if you include some code for Karatsuba multiplication and the binary search part.
Doesnât python also have limit of around 7000 digits or something? 10^5! is large enough to give RE in python (and specifically RE, not WA or TLE afair)
EDIT: Ok, I did not exactly count number of digits in 10^5, so if its less than the limit, it should be fine.
Yes u r correct but in this question the constraints are not given so I assumed that if many solutions are correct then may be N is 105 ⌠but when admin unlocks solution âŚthe solution aretotally incorrect so there is no other approach (other than brute force ) , u can see some of the solution even print nothing and passed âŚ
If the outputs wouldnât show that even the judge of the problem is wrong you could try to guess the constraints in N by using assertions (binary search).
Anyway, I think a good approach would be using karatsuba as galencolin suggeted but before the multiplications you could easily count the trailing zeros by dividing the multiples of 10 and pairs of number multiples of 2 and 5.
How did the solutions which didnât do anything pass? Iâm very confused.
ask CC
That looks like O(n^2)
its total number of zeroes, not trailing zeroes
This is an external contest from 10 years back. Itâs obviously messed up a lot. Just ignore it.
i had read all comment before.
And sorry for my inexperience in python. But what i read that python 1000 depth limit for recursion by default and itâs iterative limit is defined by memory provided by the system. So even if you use python there are limitation. But again we are not research students who have to deal with large valueâs. And judging from the review of experienced coderâs it doesnât have any better approach so this question is completely useless for CP. Fun part is i tried to submit already accepted sol. and that also gave WA.
howww?
ok
lmaooo howâs that even possible ??!!!