Count total zeroes in N! (not trailing zeroes )

Ouch!! My eyes are hurting🙄

1 Like

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 :stuck_out_tongue:

Maybe you can use other multiplication algorithms with better asymptotics, but most of them seem to have terrible constant factors.

5 Likes

It would be very helpful if you include some code for Karatsuba multiplication and the binary search part.

I don’t know how it works, I just know it exists

Here’s a library that has it, though

1 Like

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.

1 Like

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 …

1 Like

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.

3 Likes

How did the solutions which didn’t do anything pass? I’m very confused.

ask CC :slight_smile:

like this ? Find the Factorial of a large number - GeeksforGeeks

That looks like O(n^2)

1 Like

its total number of zeroes, not trailing zeroes

1 Like

This is an external contest from 10 years back. It’s obviously messed up a lot. Just ignore it.

4 Likes

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.:joy: :joy:

1 Like

howww? :joy:

1 Like

ok

lmaooo how’s that even possible ??!!!

2 Likes