7 kyu
Greatest common divisor
3,628 of 18,272RVdeKoning
Loading description...
Algorithms
Fundamentals
Recursion
.avif)
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.
in the verification test, on the Assert test:: That (mygcd (2672, 5678), Equals (334));, I get 668. And 668 is the largest common divisor than 334.
668 doesnt divide 5678 without remainders
This comment has been hidden.
This comment has been hidden.
You definitely went wrong with not using code blocks when posting code :D
Please see https://docs.codewars.com/references/markdown#code-block
Thanks corrected
This was very difficult for a 7 Kyu kata and most of that difficulty comes from the optimization stage. I do think optimization can work in 7 Kyu, but not on a somewhat complex problem as GCDs.
CS: One equal sign is missing from initial code:
should be
fixed in fork!
TypeScript translation.
Approved, nice fixed and random tests there ^^
Oh, I was wondering if others would like them. I will check what frameworks need update and maybe I will make similar tests there.
Man, this one was hell.
Random tests in NASM can generate zeros.
Tests in NASM seem identical to C's. I assume the problem is for both languages?
Yes, in C too.
fixed for both
Nasm translation
Approved :)
Go sample tests:
Fixed, thanks.
Seems tests don't get actualized. I guess with this new fork approved it should be ok (reject if it's useless): https://www.codewars.com/kumite/627ebed6ffea1073bbdd33c2?sel=627f90c7f1b9ed001ab7ceb3
This comment has been hidden.
Try to use braces systematically, your code will be more readable and this may be the cause of the error (and if it is not it will be easier to catch the problem).
This comment has been hidden.
Read my answer to TechnoDiver just below ;)
This comment has been hidden.
Because this method is too slow. You need to find a more efficient approach. This is one of the best known maths algorithms in history ;)
Can you delete your duplicate post below please?
Not efficient enough. There's a famous math algorithm to find the greatest common divisor
(author is inactive)
[approved] * 2
this was a quite dificult
This kata is a subject to deduplication process here: https://github.com/codewars/content-issues/issues/64 . Please join the discussion and help us identify duplicate kata and retire them.
This kata was voted to stay.
This comment has been hidden.
This is a question, not a suggestion. With only the condition we can't know what's wrong, how x and y change in your code? Read this: https://docs.codewars.com/training/troubleshooting
I pressed suggestion instead of question, pardon brothers and sisters.
COBOL translation.
approved
Cool kata.
ouff !! haha tricky one
C++ translation kumited
Approved
C Translation kumited.
A minor typo in the description: ".., so
thethe greatest common divisor will .."It took me a while to figure it out, but I did it without looking up the solution. Very satisfying!
Description does not say that import is banned. Change test cases or description to match. (python)
Removed the anti-cheat since it's kinda pointless anyway
Test.assert_equals should be used, gives more valuable feedback. (python)
Done
Python 3 should be enabled.
Already done
this can not be 7kyu it is much harder
what? it's just a simple math problem... Also, see https://github.com/Codewars/codewars.com/wiki/Kata-Ranking
This comment has been hidden.
This Kata is pretty nice but the numbers it has in the submit tests period are absurd!
I can't submit as I am getting the Timed Out error (exceeding 12s)..
Not a kata issue, see the tags:
PERFORMANCEis there so naive solutions won't pass.Is in the description too.
Java Translation added
Approved
I can't believe that some of the folks came up with a legit one liner for that :|
This comment has been hidden.
This comment has been hidden.
PHP Translation Kumited, please accept :D
This comment has been hidden.
yeah it is not allowed to use the gcd method of the Fixnum class, you have to find the mathematical expression yourself.
This comment has been hidden.
This comment has been hidden.
Unfortunately, the code is slow: you are checking for every possible number smaller than the smallest value of x and y. That is called "brute force programming" and although it will generate the correct value in time, it is not very efficient for large values of x and y (test cases involve numbers as large as 1.5 billion).
To solve this Kata, you have to find an algorithm that is much more efficient.
Hi, I'm trying to submit a solution but it doesn't pass one of the kata tests... this is the output I see (third line is red)
Test Passed: Value == 1 Test Passed: Value == 12 Expected: 334, instead got: 2 Testing gcd(10927782,6902514)= 846 Test Passed: Value == 846 Testing gcd(1590771464,1590771620) = 4 Test Passed: Value == 4
Is it possible to see the test case for the one expecting 334?
sure, I adjusted it so you now can see the test case
PS: I adjusted it for JS, Python, Ruby and Coffeescript. I don't know how to add a line of text including the test case in Haskell
Excellent, thanks!
Working on this in Python, and I get to the fourth test which I fail, and it tells me 1 should be 334, but I can't see the input numbers, so it's difficult to find the bug.
It later occurred to me that I should be able to write my own tests to determine the source of the bug, so while I was working on that, I discovered my bug, an indentation error.
are you sure the test did not specify the test numbers, because it should print the test values before testing your code. Anyway, I'm glad you find the bug
I'm sorry, you were right, it didn't show the input values. I have now adjusted this, although it has come a bit too late for you now. Anyway, thank you for notifying me.
I had a quick look at all tests/implementations. All seemed fine, so I thought this might be a good time to approve your kata. Congratulations on your first approved and published kata!
Great, thanks! I'll try to make my next Kata a bit more challenging ;)
Translated into JS and Ruby: two new languages to enrich this good kata :)
I am not aware of any prewritten gcd function in either language, but if given correct feed, I can try to block it.
Also, added a good deal of random test cases with huge number that should hinder both sloppy and cheating solutions.
This comment has been hidden.
This comment has been hidden.
Haha, thanks Giacomo! I added the random tests as you suggested, good idea. I also added a Coffeescript translation. I guess you, as an Italian (at least, that's my guess. My apologies if I'm wrong!) must like that language as well ;)
You guessed right about nationality (though I apparently have little pride and mindest of your average Italian Joe), a little less right about coffee: I only had a sip of it in my whole life (another aspect of my poor italianness :D), though I know a thing or two about it from my days working as a kids in various bars ;)
[While, at least according to your twitter profile, I guessed right from your "royal" surname that you must be a Dutch. Now, that's a great contry and loved my days in Maastricht <3]
Correctomundo!
Haskell translation kumited. I've used the same test cases for the user example tests, since it doesn't contain the solution (uses the predefined
gcd, which is forbidden as import). The random numbers will be between10^1000and10^5000, which should be large enough to block trivial solutions.Cool! I approved it. Although my Haskell abilities are insufficient to judge if this translation is complete, it looks as though it it is. And if not, we will surely get feedback on it soon enough :) Again, thanks!
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
I think I fixed it. Could you please check it? Thank you for your time!
(I tried your codes above, those do not pass, but maybe you have another clever way to import gcd...)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
thanks for your suggestion! Do you know a way to block it? I am relatively new and I have not found a way to do this yet...
Okay, I think have fixed it! Could you please let me know if it meets your expectations now?