5 kyu
Number of trailing zeros of N!
13,231 of 56,868Ivan Diachenko
Loading description...
Algorithms
Logic
Mathematics
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
You're solution is to slow. Read the end of the description:
Oh, thank you! I was in a hurry without reading it completely, as always)
Nice kata, but a bit overrated in my humble opinion. It's a pure math, not testing your programming skills, so the solution is really simple.
This comment has been hidden.
BRO WHERE THE HELL ARE MY TESTS CASES THERE'S ONLY 3 GOD DAMN TEST CASES FOR ME WHILE OTHERS HAVE LIKE TON OF THEM i dont know if this is exclusively targeting me or a feature for everyone else
It's okay, everything's fine, just take a deep breath, calm down, and tell me once again, calmly: what exactly you think is wrong?
This comment has been hidden.
Found a way to solve it through string in like, 2 minutes, but knew it was too easy and I was right, my solution could work with very small number but as soon as it surpass the limit of the data type i used in C it started to be inaccurate... After some research i realized it was just a problem based on a math trick, i am kinda dissapointed, but I still had some fun solving it for small numbers!
This comment has been hidden.
please make sure to read the description carefully before raising issues...
not very helpful but thank you
the description tells you exactly why your current approach will not work.
It works . I passed all the tests but it doesnt allow me to submit. Probably i shouldn't have used the factorial but i imported the sys to expand the limit. I don't mean to waste your time. Thank you
i mean, have you tried it on your computer ? check out the sample tests, there is a call
zeros(1000000000). run that on your computer and see how that goes...I found the solution thank you
I can't solve this Kata nearly 6 month))) But eventually I got it!!!
(JS) I found a way to find the amount of trailing zeros, but apparently the test cases are huge. Basic tests were barely passed in 8.8s, with many more random tests completely timing the code out.
Now what?
This comment has been hidden.
You're doing a large amount of unncessary work. Your logic is on the correct path, but you need to avoid going over all the numbers.
Is important to see the docu if kata offers to you ;)
Challenging but fun and also surprisingly simple
This comment has been hidden.
This comment has been hidden.
Remove this line:
From your code, indent
x = 1properly.I spent half a day solving this kata, and when I finally found out the solution, I was surprised by the simplicity. Just imagine that you have just started programming and the solution to this kata will come by itself!
Yes, I had forgotten my a bit of my basics there and that really held me back when I wanted to write the code.
This comment has been hidden.
This comment has been hidden.
There are two problems with your solution:
n = 30,30!has 32 digits but JavaScript'sNumbercan hold ~16 digits at most. When your values get larger than 16 digits, the least significant digits are lost and you cannot use them reliably for this problem.ncan go up to1_000_000_000. Calculating1_000_000_000!will take forever, and your naive solution will not work because it will be too slow, and will eat up whole available memory.You need to find some better approach than calculating the exact value of the factorial.
aight thx
Check the hint at the bottom:
This comment has been hidden.
This comment has been hidden.
Not a suggestion. Please do not post hints without a spoiler flag.
This comment has been hidden.
I know someone had replied earlier. But I'm sorry to say, its just not a solid argument that 17k other people have compeleted this. I know I wrote perfectly working code. If your tests can only work, if you coded it a very specific manner, then the entire kata is flawed from the ground up. It doesnt teach anyone anything if you have to go do a google search to get the solution.
Your perfectly working code doesn't work for the input range. You can't ask for a smaller range so your code works. The kata is not flawed and not all the people who solved it had to google how to do it. Sorry if you didn't like it, but it is what it is.
What you should learn from this kata is that which algorithm you use, depends on the input values. The description literally says you shouldn't calculate the factorial, so don't expect doing the opposite to work.
This is not exactly correct. to sovle this kata, you do not need "a very specific manner". You need to find a way which is fast enough, but there is more than one such way. The slow ones will not work, but all fast ones will work. You need to use any of the efficient algorithms.
Counting with fingers will not work either, you will run ouf of fingers. Does this mean the kata is wrong?
There isnt a way to run this kata without timing out the test engine. You need to lower the test numbers.
But there is, see how 48933 persons have already done it. The tests are fine, read the hint in the description.
you really need to undertand the math sintaxe to do this kata, but maybe an AI can help you to describe the math formula for you :D
This comment has been hidden.
This comment has been hidden.
Try 9-digit numbers, up to 1e9.
Whoops, I tried that on Microsoft Edge's Javascript menu, and Edge ended up consuming most of my CPU. I had to force close the browser via Task Manager, LOL! I'm skipping this exercise.
More of a math problem, not a programming one.
Мое решение считает n=1000000000 за 2секунды. Но все равно получаю ошибку Timed out
Not a kata issue. Look for a faster solution. And please write in english next time.
For some reason, the last two tests are the ones that are practically impossible to run. I tried to find the factorial of 1000000000, and my computer ran past the time allotted by the server.
Also, sometimes the big numbers are not processed after the number of digits in a factorial passes 4300. Even using
sys.set_int_max_str_digits()slows down the process by a lot, even after updating the numbers.Read the hint. Not a kata issue.
Hi, I am facing issue using BigInteger to calculate the factorial. Could you help me please (java)?
BigInteger fact = BigInteger.valueOf(1); int counter = 0; for (int i = n; i >= 1; i--){ fact = fact.multiply(BigInteger.valueOf(i)); }
look at the description - you are not supposed to actually calculate the factorial. It's more of a math quiz. There is a way shorter more efficient solution.
How do you expect to pass
n = 1_000_000_000with this?Python update (new testing framework)
Approved
This comment has been hidden.
It's a bug in your solution, not a kata issue.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
I was about to post this purplemath link. Mathematically challenged, I found it more helpful than the link in the instructions.
I'm pretty sure I've got the correct solution (one from the link attached) but it times out before it can complete, which seems weird
Using c++ I cannot figure which data type could store such large factorials since I cannot use boost libraries.
There is no data type which could store such large factorials, that's the point.
.
do it without calculating the factorial. it says that in the description
This comment has been hidden.
You're doing something wrong.
bro just give us the output of our program pleaaaaase
test trying to calculate a very long digit, what's reason? my code is working, but kata can't be solved because of timeout :/
The reason is to force you to find a faster solution, that's not a kata issue. Read the tip at the end.
This comment has been hidden.
which language?
Java.
This comment has been hidden.
Which language? Which issue?
This comment has been hidden.
Nice explanation, but not a kata suggestion ^^
This comment has been hidden.
Your code being too slow is not a kata issue. It's even written in the description you should not calculate the factorial.
it seems its a math problem
Yes. Nothing to do with coding.
This is hardly a coding problem. This is a mathematics problem that is easily programmed once the actual problem is solved. I suggest no more math problems, riddles, gotchas, or "this one clever trick" katas. 0/10
So, what's the suggestion for this kata?
Hi @slintak and welcome to Codewars; if you are a new user you are probably using the "next kata" functionality which suggests level appropriate katas.
However, if you have a clear idea of what you do, and do not, want to solve/practice then you might be interested in the search menu where you will be able to select the topics you want to practice. In particular, if you go to the Tags search bar and avoid katas with "Mathematics" or "Puzzles" you will be able to concentrate on the kind of katas you seem to be interested in.
I agree
0! = 1, not 0. so first sample test are wrong
The kata asks for "the number of trailing zeros of
n!"Since, indeed,
0! = 1: how many trailing zeros are there in1? There are no trailing zeros, i.e. 0 trailing zeroes.Hence the expected correct answer is 0.
i solved it already
This comment has been hidden.
Probably due to the time complexity of your solution. I'm currently working on this kata and came up with a solution that works, but it takes too long after trying 100000! and 1000000000!. So, got to figure out a more efficient way to code the solution now.
Very interesting Kata, i sure learned something new on how to process certain problems! Thanks!
Not a programming problem but a math problem.
While not uninteresting it itself, most people go to codewars to practice programming, not number theory. The problem isn't bad, it's just not suited for here.
I have not tried to solve it with loops and stuff, but given how the problem was phrased I suspect that there was a check for efficiency, which can only be passed by solving / googling the math problem but represent zero coding difficulty.
Edit: I'm not a hater, I solved it quite fast. I'm just objective.
I disagree, you should use the right algorithm for the task at hand. And that's part of a programmer's work.
A programmer would solve this in 1mn googling if he doesn't already know the maths solution. There's zero practice here. 1mn googling, 7kyu level coding.
Besides, I'm not planning to become a programmer, I just want to practice the languages I'll use later and learn things about them in process. Does your comment mean that I shouldn't be on the site because it's only targetted at people who want to become programmers?
much of a programmers work involves googling, there's no shame in that. but to answer your query:
choose a kata that you feel is worth your time. no one is compelling you to do number theory tasks
DMorg, I didn't say that, at all. You said this wasn't a programming task and I disagreed.
This comment has been hidden.
You've answered your own question: what's wrong is, that it runs out of time.
You need to find a more efficient (faster) algorithm - currently your approach takes too long to find answers for inputs such as
n = 1000000000.This comment has been hidden.
Short code does not necessarily mean it is fast :P
Only thing you can do is reduce the number of steps to solution, viz. removing loops, taking shortcuts through mathmatics, &c.
That, or skip it (not recomended).
Look at hint at end of the kata. Probably you doing it wrong way.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
.
All I can say is, brute force is not the solution, as random tests give n to a billion. No amount of optimization will help.
In short, the test is not for programming, but for mathematics.
Like everything else here, the test is about solving a problem using a programming language.
I'd add in a limited time.
This comment has been hidden.
Apparently, it's not about rounding, by the way, int () rounds down to a smaller integer
Swift sample tests:
Fixed
passes all tests but fails at random tests such as the following -
Testing with n = 97974760: expected 24493689 to equal 24493686
So don't say it passes all tests.
It seems that
24493686is the correct answer: https://www.wolframalpha.com/widgets/gallery/view.jsp?id=54da27e6e09dc404890a578735b9f7d8This comment has been hidden.
Out of curiosity: how long does actually last your program with
n = 1000000000(this is one fixed case, and the upper bound for random tests).This comment has been hidden.
This comment has been hidden.
approved by someone
D translation
approved
Neat trick, but definitely more math than coding.
Factor translation
Approved
wrong kata. Execution Timed Out (16000 ms) but in my IDEA all work (981 ms)
The kata is perfectly fine, it has been solved more than 36,000 times. Out of curiosity, how long does it take on your ide with
n = 1000000000?oookay... you are right. I need to optimize...
So, how long? ;)
eternity XD
^^
This comment has been hidden.
It's hard to say, but looking at your code I'm guessing you are failing at the test case where
n=0which will lead to yourtmplist being empty regardless of how you change indices.In general, to troubleshoot you should first try printing the test inputs - in Python just add:
where here
nis the name of the input, to your code so that you can see in the console which inputs are causing you to fail.n=0 is the very problem
Thank's a lot :)
Lua translation!
Approved
This comment has been hidden.
This is not a kata issue (= a bug in the kata).
I doubt those solutions are instantly with
n = 1000000000.my program execution timed out (16000 ms),
but in my local it's only 5s when run
Assertions.assertEquals(536870902, Solution.zeros(Integer.MAX_VALUE));
what happen?
This comment has been hidden.
This comment has been hidden.
I don't do Java.
This comment has been hidden.
Golang version seems to be fine for me. You are not supposed to calculate the actual value of the factorial. Inputs go up to
n=1000000000, and even with bigint, calculating it will take forever.I am going to close this as not a kata issue, because my Golang solution which uses exactly the same approach I used in other languages passed.
Thanks for the reply. Then I'm on the completly wrong track…
Math based kata. Think of a more "mathy" approach :)
This comment has been hidden.
This comment has been hidden.
I can't see your reply 'cause it's hidden(
This comment has been hidden.
This comment has been hidden.
How long does your solution tun locally for
n=1000000000?It's breaking. In that case I suppose to try with another approach. Thanks fo r fast response.
DK
So happy with this one, i figured it out through a bad code first and made my way through observing and finally producing a formula for it!
Go translation
Approved, (tho I don't know Go, I can understand the syntax, so if there's any issue raised, all eyes on u, kudos 👀😏😉)
I think that's because the author asigned a big number for one of the test cases
Not a suggestion
timed out 12000ms issue. can't be done
check out the previous comment thread
i just said so :)
Execution Timed Out (12000 ms)
But this is done in 0.002s in the Pycharm
How much time does it take in pycharm for
n=1000000000?It took 193s with
n=1000000000. I understood... I have to optimaze. ThxLISP translation available. Please review and approve.
My program times out even though I have time complexity of O(n) anyone have any idea, do I need a time complexity of O(logN)?
First of all, what you think is O(n) might actually not be O(n), depending on your approach. But generally yes, you need something better than linear.
Okay thank you I didn't expect that honestly doesn't make much sense to me, but I'll figure it out
This kata is about math, not coding
Totally agree. I really try to avoid these "mathy" problems. However, once I click it open, there is a stupid stubbornness in me that makes me need to complete it. I wish these challenges had a BIG yellow warning label on them!
I first tried to solve this with factorial then realized that there is a way to solve it without factorial but it is still giving me time out message. Somebody help me, what is this mess? I think i have efficient program but it says time out.
If your program times out, it's either still too slow, or it gets sometimes lost in an infinite loop. It's impossible to help you more since we have no idea what you are doing. In all cases, this is not a very hard problem, with some basic maths and thinking it's possible to solve it. Giving a hint would be spoiling the solution. If you can't find a proper way to solve it maybe you should move on to other katas, someday later, after solving more problems the answer may appear to you as an obviousness :)
logical and mathematics, but not programming
This comment has been hidden.
Try to run following test case and see if it works:
Test.assert_equals(zeros(1000000000), 249999998, "Testing with n = 1000000000")To say the truth, I would not recommend spending a lot of time solving this kata if your goal is to improve programming skills rather than math.
Using the right algorithm for the task is a programming skill. But you can always skip a kata, nobody forces you to complete it.
This comment has been hidden.
Not a suggestion.
Execution Timed Out (12000 ms) and can't do anything with it, but in MS VS 2019 all working fine. C++. Basic test passed.
How long does your solution run in your VS for n=1000000000?
same
How long does your solution run in your VS for n=1000000000?
This comment has been hidden.
Please use a spoiler flag.
This comment has been hidden.
timed out from too big of a number when using long datatype. In Java
You don't have to calculate
n!; actually, you can't.why top solution is failing the test ?
If you mean python, the top solution used python 2
Yup. Python. ok. :)
there is some kind of issue in this kata because whenever I am running it throws an error but works flawlessly on my machine(vs code)
To properly report an issue, mention the language and which error do you get. Read this: https://docs.codewars.com/training/troubleshooting
There is no problem with Python:
The hard part of this for me was finding the solution to the math problem. Once you have it the code wasn't all that complex. Very fun Kata! To anyone struggling I would say to look into the math bits. I didn't find the supplied article all that helpful IMO.
This comment has been hidden.
Huh I guess I did it a different way than you then.
This comment has been hidden.
OP solved it, closing
COBOL translation updated.
This comment has been hidden.
COBOL translation.
have to wait for author to approve, the kata seems ok, I was able to verify with another solution
COBOL translation kumited
do not approve for now
(i will come back and fix it in a couple of houtd
Ok, take care :)
It has to be approved by the author anyway. Perhaps you could unpublish for the time being?
Oki doki, kumite is here :)
I republished by mistake and seems I can 't unpublish again. PLEASE DON'T APPROVE for the moment, I'll do a new suggestion for approvals when problems are fixed.
If you're struggling, Please read the Hint carefully think smartly. This task is more about math rather then programming. Thanks for this Kata, I had fun. cheers
Reminder != kata suggestion
This comment has been hidden.
How big are the test cases ? I tried timed it with
perf_counteron my laptop and it took 3.05 seconds for a 7 digit number. I don't understand why it would time out on codewars... Could anyone help me out ? Thanks !In Python N is as big as 1000000000. Note this:
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Found it. If you allocate your Z as a double, it will sum the decimals in the equation, giving some extra zeros at the end. However, if you allocate Z as an int, it will give less. And while I think that should be wrong, the corrector program gives its 'all clear' to that other number.
This comment has been hidden.
time out？ zeros(10000) about 10 seconds
why is timing out even a thing
Because it would be somewhat infeasible to keep the server running for two days straight, spinning its CPU, eating resources, and waiting for the answer which can be reasonably expected to be returned in seconds.
was being rhetorical, truthfully i was just frustrated coz im too dumb to figure out how to solve it without timing out.
This comment has been hidden.
This comment has been hidden.
Your code takes too long to execute. You have to reduce your execution time to under 12 seconds. You need to find a more efiicient way of getting the answer.
This comment has been hidden.
OP solved it, closing
If you want to solve this problem with the least code, you must first find out the law, and then this problem is more like a mathematical problem
This comment has been hidden.
30! = 265252859812191058636308480000000 That's seven trailing zeros. You must do something badly. Moreover use a spoiler flag when giving elements of solutions. Thanks.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Please don't spoil solutions, thanks. Take a pencil and a paper and check for this, it's pure logic.
This comment has been hidden.
This comment has been hidden.
I really struggled to find the solution for this kata, but I have learnt a lot (and also got the 6 kyu) :).
If I can give a piece of advice for people who doesn't know how to face this kata, Prime numbers can help a lot.
This comment has been hidden.
I'm very new at katas, I tried with memoization but it wasn't fast enough. Spent 30 minutes and i finally found an obscure number theory formula to find the prime factorization of a factorial Implemented it, it looks very ugly and sketchy, but it's ultra fast and it does the job. Look at the best solution among the ones posted. It's a super elegant 1-line piece of code. My soul is Crushed
I liked this kata a lot, thanks to the creator
1 to 30 multiplied is, as number : 265252859812191000000000000000000 But the test awaits 7 as correct answer ? Did i miss something here ?
1 to 30 multiplied is, as number: 265252859812191058636308480000000. It has seven zeros at the end.
This comment has been hidden.
This comment has been hidden.
Your problem lies in
i <- Range(0,n+1,5), linear solution will be too slow.My Scala solution runs ~6.5s, so Scala version seems to be OK.
This comment has been hidden.
From: https://coolconversion.com/math/factorial/What-is-the-factorial-of_30_
Seems like 7 zeros to me.
https://www.calculatorsoup.com/calculators/math/scientific-notation-converter.php?operand_1=2.65252859812e%2B32&action=solve and google calculator says 30! = 2.65252859812e+32
calculator soup must have something else going on. Agree with others though, little too mathy on this one for my tastes.
https://www.calculatorsoup.com/calculators/discretemathematics/factorials.php
Scientific notation loses precision.
Your solution is buggy and it returns incorrect results. Now you can choose between hating on the kata, or learning what you did wrong and how to fix it. Your choice.
The problem of implicit conversions causing data loss is a real life problem which bites unaware programmers quite often. It's up to you to decide whether you want to know how to deal with it and fix it, or get upset over a problem which you yourself introduced.
Relax hobo, please be kind, world is already an ugly place.
Thank you @Chrono79 -- that makes sense why I was confused.
I agree that is more of a math problem than a programming one
This comment has been hidden.
Try to run your solution locally in your IDE for n=60 and see how it
worksfails with your debugger.done it by testing. but still time out problem for taking points !
Issue with your code, Try using a more efficient algorithm, read this before raising issues next time ~~
The author should have knowon that Python is slow and not capable of doing all of this under 12000 ms instead of putting unnecessary tests that are impossible to do under 12000 ms
My code is just 2 lines (could have been 1 but this is for better excution time) and it still gives me an
Execution Timed Out (12000 ms)Error.I'm not using for loop, or while loop, or anything that could be possibly slowing down the program, I am just using math library (which is pure C) with len, strip functions (which are pure C too)
Number of tests are scaled as per the total time (runtime + compilation time) of languages hence the required time complexity is roughly same across all languages.
and I've done this in python.
Yeah I ran into this issue as well it is really quite silly
That's not a programming task, but a maths task. Downvoted.
P.S. It was useful for me tho since I missed the hint at first therefore learned new things about the language. Thanks my unattentiveness for that. :)
This comment has been hidden.
Great kata. Thank you for fun that this kata gave us:)
This comment has been hidden.
Don't check every number for divisibility.
The third test for python is wrong. It says:'Testing with n = 30: 9 should equal 7.' However, there are 9 zeroes in 30!.
The keyword is trailing
I made a soultion and I'm getting an excution time 12000ms out for some reason. When I set a console.time(), the function run less than 70ms for n = 100000.
That's for only one test case, this kata is testing for 100+ test cases, random ones included. By the way,
I'm not calculating the true factorials though. It is passing all the tests. For the case of n=100000, it is returning the correct number of trailing zero in less than 70ms. That was the longest test that ran. Where n<100000, the time it took to return was much faster.
I got the solution, however, I do think they should do a better job of clarifing their basic tests.
This comment has been hidden.
This comment has been hidden.
what do you mean that wasn't even easy, jesus, took me an hour
For the C solution even if I pass all the tests and use the same method definition as in the tests I get this error and solution is considered wrong because of it:
fixture.c:28:60: warning: format specifies type 'int' but the argument has type 'long' [-Wformat] if (user != result) printf("%d should equal %d\n", user, result); ~~ ^~~~ %ld
It's a warning, not a error, so you can ignore it. This isn't the line that makes your code crash or fail. ~580 C completions says to me this is problem with your code, not a kata issue. Closing...
My solution, which uses recursion, seems to work perfectly and in under half a sec on vscode Jupyter notebook using n=10000, but am getting a maximum recursion depth issue on codewars
How large
ndo you receive when testing your solution on Codewars? On C# and C++ncan go up to 1e9, and I believe that in Python it's similar. 10000 is probably too small to prove correctness of your solution.This comment has been hidden.
LOL, I made my own factorial functions ,it timed out i used math.factoria() it passed the basic test but show timeout error for the attempt cases. I used my code on repl and it worked perfectly. I am figuring out how to came up with an optimal solution.
Exactly I think i found the pattern of zero. there is no need to find factorial. I think
This comment has been hidden.
You should mark that comment as a spoiler, not just say so.
This comment has been hidden.
Isn't that O(n)? Never heard of N(O).
Sorry for my monkey stupidity :D you're absolutly right, there is big O problem I wanted to say
Well mine works for the tests, but times out whenever I try to Attempt. Don't know how else to do it with out using a for loop
Try a math approach.
see the first 100 factorials and check the similarities . answer will come
i haved problem in data type range in c++ which data type have enough to save fact of 30
You shouldn't do it.
This comment has been hidden.
Im thought and did right. Great kata... Thank you.
This comment has been hidden.
Attention!
30!has 7 trailing zeros: https://www.wolframalpha.com/input/?i=30%21Tests in JS seem to be OK.
Kindly, see the value I get for 30! below:
30! = 265252859812191030000000000000000. But if 265252859812191058636308480000000 as confirmed by 2 professionals is what 30! is, then I will have to check my values again.
Thank you for the feedback.
That result looks like what you used can't represent so many digits and it's losing precision.
I am not a professional factorial calculator, no. But as Chrono said, it seems that your calculations are losing some precision somewhere, probably because they overflow
MAX_SAFE_INTEGER.If it's the case, it would mean that you missed the hint at the bottom: "Hint: You're not meant to calculate the factorial. Find another way to find the number of zeros."
fac of 30 is 265252859812191058636308480000000
This is a great kata. Click the link to provided in the description to understand the problem. Then take a piece of paper and try. Don't give up try to understand it, it's very simple. Looking for great katas in the future from the author 😉
My code Passed: 108 Failed: 1 , Testing with n = 49257472 - Expected: 12314363, instead got: 12314362 as you can see the difference between the two numbers is 1. Does anyone experiencing the same problem ?
Did you find the solution for this? i'm having the same problem now.
Still no solution for this problem
Same here, getting sprodaic failures on random tests
This comment has been hidden.
This comment has been hidden.
It depends, but there's a big change that you are trying to calculate actual factorial, and this is not the way to go. You need to find a way to determine amount of zeros without calculating
n!. Writing down several terms on a sheet of paper and finding a pattern when a new zero appears at the end is a good first step.Read the hint at the end.
:(
This comment has been hidden.
There is already a hint at the end.
Oh! Didn't see xD
This comment has been hidden.
Note that you are off by 1, exactly, in one corner case.
This comment has been hidden.
It'll sound obvious, but find the algorithm which is 100% accurate.
yeah, found it!
has anyone been able to execute python programs in less than 12 seconds?) I have tried various algorithms, including recursion, interation for, reduce, but the factorial 1000 exceeds the time
This comment has been hidden.
You should not calculate the factorial
This comment has been hidden.
You don't need to prevent "scientific notation". Scientific notation is just... notation. Why would it matter what kind notation is used? Notation has no impact on calculations (not in this kata, at least).
What you have to avoid though is overflow. The "scientific notation" you observed is a symptom of the fact that your numbers overflow MAX_INT at some point and turn into imprecise floatign point numbers. Large FP numbers are represented with scientific notation, so what you observe is just a visible symptom of the fact that your calculations overflow and your numbers lose precision. Find a way to get the answer without overflowing, keep calculations precise, and you will be good.
*e+20is not your problem, but30!is.I get execution timeout when executing!!!!
@collinsmarra thank you for your efforts. Execution timeout means you should build a better algorithm in terms of Big O notation
That's too bad! You need to think of some better, more efficint approach, because trivial approach will definitely not pass!!!!!
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
code works perfectly, tested it myself with large numbers, passes all the tests but then i get this message
STDERR FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
what am i doing wrong? :)
Are you trying to actually calculate the factorial? If not, you might be running into some infinite loop.
This comment has been hidden.
Still, somewhere, somehow, your solution allocates large amount of memory, exhausting all availale heap space. It's difficult to say why without seeing the code, it can be some large array, some long string, or some large bigint. Make sure you removed all traces of your old solution, and use only new, efficient one.
This comment has been hidden.
If, for example, n=1_000_000_000, your loop performs 1_000_000_000 iterations, your array grows to 1_000_000_000 elements, and you divide n by 5^1_000_000_000. Is that really necessary?
thanks a lot! figured it out with your help :)
Factorial with haskell is not working and always yield in timeout, while I tried the same in ruby it worked.
RTFM!
There's no way you calculated factorial of 1000 in ruby... Whatever the case, this isn't a kata issue.
What worked? You haven't completed the kata, and you're not supposed to calculate the factorial in any of the languages.
This comment has been hidden.
Your solution being too slow is not a kata issue.
This comment has been hidden.
Spoiler...?
I don't think this comment is spoiler coz there is the same hint in the link below kata's description. It directly points out to use this method in it's formula :)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
There is a bit of math involved, yes.
This comment has been hidden.
looks like u solved it~~
This comment has been hidden.
Because numbers in random tests are HUGE. You need to look for another approach.
This comment has been hidden.
Your solution does not work for , for example, 500.
Thanks for response. Can you give me tip, how i can fix it, if im using LONG and its not enough?
Yes, you can start with reading the hint at the very bottom of the description. Or you can try a pen and paper and calculate successive factorials to see when a new zero appears at the end of the result.
Ah. Thank you! Now i see how zeros changing
This comment has been hidden.
This comment has been hidden.
It would be nice if the upper and lower limits of N were specified.
a good algorithm should always work!
I believe for scala
should be assert(Solution.zeros(14) == 1) not assert(Solution.zeros(14) == 2)
No,
14! == 87178291200there are two trailing zeros there.Random cases do not work due to resulting integers in calculation being too large with JavaScript (memory overflow). Codewars does not allow us to use a newer version of node, so we can't use BigInt to work around this. If there is some other way around this problem, I think that needs to be mentioned in the description.
It's already there: Hint: You're not meant to calculate the factorial. Find another way to find the number of zeros.
Also, even if you were able to use BigInteger, there's a high chance that it still would not work:
n!would take forever to calculate, or would not fit into memory. And rank of the kata being 5 kyu somehow implies that solution is not as trivial as just multiply and count zeros, as this would be definitely ranked lower. That's all what problem solving is about: there's a problem which is seemingly easy, turns out to be harder than expected because it grows rapidly, and you find a way to reduce and shrink it back to the form which can be easily handled. The essence of programming!Good luck and don't give up!
This comment has been hidden.
It's written in the kata description that solutions like that won't work.
I though I wasn't calculating the complete factorial, but off course that was only true, when the factorial produces zeros. Which makes me realize I really don't need the (incomplete) factorial, only the last digit of the factorial. But even then I get a time-out. Am I just thinking in the completely wrong direction?
looks like u solved it~~
This comment has been hidden.
It's already in the description.
This comment has been hidden.
The code for importing the math library is:
import mathHope that helps
This comment has been hidden.
Not a kata issue, it's a problem with your code, the tests go up to 1000000000.
Also, please, next time mark your post as having spoiler content.
The larger numbers are producig a marginallly different result. Hence failing the tests.
use BigInteger to store your resultant
My solution is not very optimized but works. And I cannot validate this Kata because Execution Timed Out (12000 ms).
Same here. Its more of a mathmatical question rather than complex algrithoms
This is really just a math trick. The coding part of this problem is very simple once you know the trick, but if you're not a mathematician then the information in that link is nearly indecipherable.
Exicution keeps timing out. It's possible that test cases are too large. Otherwise I will have to figure out how to optimize one loop (which should be 0(n)).
Not a kata issue. Test cases ARE large, and O(n) solution won't work. You need to look for more general solution without loops.
Thanks, I'll do my best!
This comment has been hidden.
Figured it out... took forever... but now I know more about optimization and math then I ever wanted to. Thanks :3
php translation kumited
This comment has been hidden.
OP solved it, closing
This comment has been hidden.
The input
ncan be10 ** 10so a linear time solution would be too slow.Also, if you post your code, please remeber the spoiler tag.
oh, thanks for the answer, and will be pay attention to the spoiler tag next time.
Julia translation
Approved
Not supporting BigInt
This comment has been hidden.
Mark your posts as having spoiler content next time. BigInt is supported from Node v10.4 onwards.
This comment has been hidden.
Iterating up to N is not efficient enough. There's 100 tests with similar numbers that you tested, so that's why it times out.
Oh. Thats explain everything, thanks.
Prolog translation kumited. Please review.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Which part of the sentence "You're not meant to calculate the factorial" do you not understand? You'll never solve the task this way.
This is funny. So how one supposed to come up with number of trailing zeros of a number if you can't have the number to begin with ? Duh ! Leaving this one.
This comment has been hidden.
Add test:
This will filter out solutions that fail due to Integer overflow for higher
n's.This would change the kata requirements, wouldn't that? And some languages support arbitrary integer size, so your suggestion means introducing language-dependent requirements too.
Agree about introducing language-dependent. But how can that change kata requirementes? The point is incorrect solution can pass the tests and be accepted. Taking into account your notes, what about adding such test:
assertThat(classUnderTest.zeros(429496730), is(107374174)); //Integer.MAX_VALUE / 5 + 1It is the minimum number (but stil 32 bit) that can detect java int overflow. Though there is no limit onnin kata description...This comment has been hidden.
Please don't post solutions in discourse, it's forbidden, and please always use spoiler flag when posting code (or anything spoiler worthy).
Not necessarily an issue with this kata in particular, I just can't find a place to report something with the code interpreting itself.
In C# it returns number^0 as number, not 1. Had an idea to use exponents to get an answer without calculating the factorial, but that little hiccup means having to write a lot of code that should be unnecessary.
This comment has been hidden.
This comment has been hidden.
You've already answered your question. There's a trivial mathematical trick which you can (should) use to calculate the number of zeroes. If your code is
O(n), it is already fundamentally wrong, and you should search for another solution.This comment has been hidden.
This comment has been hidden.
Not necessary. You shouldn't calculate the factorial.
Can someone confirm if the C# test cases are working? I pass the local tests, but the server-side ones I get the following errors:
BasicTests Test Failed Expected: 1743 But was: 1744
RandomTests Test Failed Expected: 207049518 But was: 207049524
As you can see they are rather close, so I would like to make sure it's not some sort of server buffer problem. I'm implementing the solution that Wolfram provides in your link.
This comment has been hidden.
This comment has been hidden.
Your solution is too slow obviously.
IMHO, any solution using recursion should be rejected.
you will change opinion when you will see that in fact, recursion is the only one way to go with for fast.
recursion is not working at all in this case, the only way is to use mathematical algorithm for this problem
This comment has been hidden.
Your solution is O(n^3), pretty slow. It needs optimized.
Also, this is a question, not an issue.
Not an issue, yes. @jerome: you need something more efficient (it's not about optimization, tho. It's about finding a better algorithm)
ho ok, i'm surprise but well... i have to work more on this. Thank you for check my code and provide an answer.
Sum over a range is
O(n^3)? You should work on your knowledge first before "teaching" others.I gotta say... not satisfied with this test. I managed to get it done, but after many hours. When I ran several of valid answers, which ran on a very good time on my pc, I got the error 'no data was written to STDOUT or STDERR'.
Also, several answers of mine were rejected because the end result was float.
However, when I checked some of the valid answers, I very saw similar answers to mine, and answers whose end result was float.
My python version, on my Jupyter Notebook: 3.7.1 (default, Dec 10 2018, 22:54:23) [MSC v.1915 64 bit (AMD64)]
same problem there. I get manage the mathematic solution who doesn't need to calcul the factorial and who have only one loop to get a sum requested for the solution. All tests are green, but attempt said server time ran out... i can not imagine what can be different to pass the server time obstruction. On my computer, there is no significative delay as long as it is very simple. In fact, i got an answer show me that my solution was too slow... i do simplification for remove the sum part, but again... too slow.
I'm a bit confused. I'm not meant to calculate the factorial. So I need to get the trailing zeros of the factorial (that I'm not meant to calculate) by some kind of mathematical stunt? Every solution I have would calculate the factorial in some way, to get the trailing zeros.
You absolutly no need to calcul a factorial for get the trailing zero in the result of a factorial. It is just a mathematic problem where only sum and power and division is required.
I really enjoyed this problem, it truly stretched out the way I approach a problem with Clojure. (I am a js dev by trade so I approached it with a JS mindest at first).
This comment has been hidden.
That code seems On2 so it's not so rare it won't work. To increase the readability of comments or descriptions, see this page in the github wiki.
This comment has been hidden.
It worked for me (translated your js code to Python), and without actually seeing what you tried, it's hard to say, next time use Question label (and paste your code with proper markdown and marking your post as ahving spoiler content), not issue, see how many people passed the kata in Python.
This comment has been hidden.
This comment has been hidden.
Then you should not fill the buffer to so much extent?
This comment has been hidden.
Read the hint, try another way.
look at my code, i didn't calculate the factorial and solution is a mathematical sum who is very quick... it should not refused due to server time error... also, what does server time error has in relation with an objective test ? I missunderstand the idea, because if the server has a full load, what does it happend ? you trash users who provide an efficient solution ?
I lost lot a time... but it gives me a great realization
Python reference solution calls the user's function.
Fixed.
This comment has been hidden.
That's because
short != fast. The kata can be solved inO(log(n))time with a simple math trick. Calculating1,000,000,000!may easily take up the whole 12 sec time limit, let alone calculating it twice.Groovy translation kumited. Please review and approve. Thanks, suic.
Already approved.
Rust translation
Already approved.
.
have next results:
Test Results: Sample Tests Should pass sample tests Test Passed: Value == 0 Test Passed: Value == 1 Test Passed: Value == 7 Completed in 2ms Completed in 4ms You have passed all of the tests! :)
but cannot push submit button, because it's not available
Try alt + enter or changing the browser zoom level, it's not a kata issue.
have passed all basic tests, but still cannot submit the final result. the button dont greened out.
In the code sample return type should be corrected I guess ;-)
In the current state, this is a math problem long before it's a coding problem. It is only after you find out the "one weird trick" for working out trailing zeroes, does it become an actual coding problem. I would argue this kata would be much better if it gave you the timing out code to start with and then the exercise was optimising the existing code rather than spending 2 hours trying to come up with a way to work out trailing zeroes.