4 kyu
Trailing zeros in factorials, in any given integer base
54 of 533Dr Phil
Loading description...
Mathematics
Algorithms
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.
OCaml translation
Approved
Scala translation
Can I hint others to 3 katas to solve before this one?
The first kata is already in the description
The second kata is about base conversion
The third kata is about primes
Those 3 katas would help a lot before solving this one
kata hint != kata suggestion
Is there any software that I can use to calculate a number to a different base, so that I can spot differences?
And is there any hint one could give to understand the problem
If you haven't implemented base conversion before then you should start with that first.
Here is a kata that might help you with that.
Thanks I solved that kata after you suggested it,
but didn't really understand how to relate it with this kata.
Solve this as well if you haven't already, this is just a generalised version of that.
The one I linked relates because you'll want arbitrary base conversion code for figuring out this one.
Thanks a lot. I really appreciate this kata.
I found another thing that would help in understanding this kata
Do you mind if I shared 3 hints to solve this kata?
2 of them are already provided, the first is the kata in the details of solving this kata
The second kata is here in this comment
And I got a rough idea on how to solve this kata
so I have a third kata that could be solved before this because the 3 of these katas contribute to solving this kata
And thanks again for your help
Chai+assert+bigints for JS
Approved
JS tests should use BigInt and be un-nerfed compared to Python.
Fixed
I think something broke with the basic test in JS, they all want 1 as output when random tests work fine
JS tests are fine.
I don't think this is truly resolved. For the first tranche ("
Trailing zeroes of") of tests in JavaScript, the parameters are always(num: 6, base: 16)Thanks for the kata, finding out the procedure to solve it is awesome.
Why Time Out on Python? :(
You have to improve the performance of your prime decomposition.
Also
10 ** 100is too low for some inputs.Thanks
7! = 5040
Please, improve desctiption
Duplicate issue
Testing for 3166824677280918! in base 3849667477
I always encounter Execution timeout in this test...
what to do?
Your solution being too slow is not a kata issue
Why num = 15 with base = 12 must return 5??? This is test fail?
15!in base 12 is191529600000, which has 5 trailing zeroes.:::ruby description:::
trailing_zeros(7, 2) == 4 #7! = 5030 = 0b1001110110000, which has 4 zeros at the end
::: 7! is 5040, not 5030. 0b1001110110000.to_s(10) => 5040,
please, improve desctiption
Fixed
Done a ton of research to be able to pass all the tests, but now optimizing to pass all the tests without timing out just feels impossible. This kata is only realistically solvable for people who've studied computer science or math. Very frustrating.
There's a typo in the description. 7! = 5040, not 5030.
Fixed
Python 3 should be enabled.
This comment has been hidden.
This comment has been hidden.
Hi, I get following error:
for all random test of ruby solution. What does it mean? Thanks
That's not an issue. That's a question.
Because CW is still eating up error messages from
itblocks in Ruby right now, it's impossible to see the error. Please post your code with spoilers (alternatively, you can check the input first, Ruby should still runputsstatements before hitting the error.It seems then the problem is in missing
require 'prime'statement in test code.Should be fixed.
I get this
Process was terminated. It took longer than 12000ms to completefor one test case. I assume this test case is with huge number for the factorial. I am using the iterative way to handle my factorial. Is there a better way to approach this long number case to pass the test case? thanks!You can see from the input (print the input out!) that there are ridiculously huge numbers.
Maybe you'd want to try this kata first ;-)
This kata is a duplicate of this one
That one has a much smaller range of values.
This comment has been hidden.
Solution setup for JavaScript has the function named as
trailing_zeros, when it should betrailingZerosas per JS convention.Fixed.
(Blame @GiacomoSorbi more about all the issues! ;-))
Approved
Maiden writing random tests, please wait warmly...
Game!
a couple of the bases are messed up please fix,
Fixed
Excellent kata, thank you!
Does the Javascript version of the kata actually work?
I don't think the number 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 in the test cases can be represented exactly since it's actually stored as an IEEE double-precision float.
I tested it and it works; the relevant test just takes the first 15 digits (I checked and JS double-precision seem to always cover the first 15 digits), transforms them into a string and then compares the result to the expected value.
Does your solution fail on that test alone?
The test comparison is not the issue. How can you determine the number of trailing zeros if the base itself can't be represented accurately?
I created a special case for the occurrence in which it is the base and I saw so did you; when it is the number to factor (is it the right term?) it can be done.
But I was wondering that myself: do you find that removing that test (the one with the big number as a base) would be more fair for the JS version?
I special cased it just to pass the kata so I could see what the tests were. I don't think it's a legitimate solution for the large number base.
The number has already lost precision by the time trailing_zero() gets it, so there is no conceivable way it can do the factoring properly.
JS only has 53-bit digit accuracy for integers (unlike the other language versions in this kata), so it shouldn't have such tests.
Fixed.
I also fixed the wrong translation solutions and added more fixed tests.
No comments yet?
Well, it is really a nice and challenging kata; I just translated it into Python, hoping that if you will approve it, it will also help getting more people on board and trying their hand.
I am also going to try translating it in JS soon, but I know it won't be that easy. Meanwhile, thanks again Dr Phil :)
JS version submitted too; it was quite a bloodbath, particularly for larger numbers, but I think I did it :)
Thanks for the Python version. :)
My pleasure jolaf and glad a skilled coder like you appreciated my work; on a side note, don't think I forgot about the last morse kata; I must just find the right inspiration ;)
:)
Can you give me a hand with Python http://www.codewars.com/kata/find-the-capitals-1 ? It looks something strange is happening there.
@GiacomoSorbi
Your solutions for the JS and Python translations are
wrong! ;-)I took the effort to put in my (correct) solution and fixed the tests.
Lovely: care to remind me what was wrong with it?
They fail against numbers with sufficiently big primes because you're hardcoding them in.
e.g:
I checked the results of my solution against the author's Ruby solution (which doesn't hardcode any primes) and they match up. So it's your solutions that just happens to pass the fixed tests ;-)
(See, that's why you need random tests!)
Ah, the joy of seeing one's code from years before: all fixed now?
Yes, I fixed everything before approving it.
Thanks :+1: