7 kyu
Count the divisors of a number
22,394 of 76,127tiriana
Loading description...
Number Theory
Mathematics
Fundamentals
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.
PHP allows naive solutions to pass, other languages require a more optimized solution.
Java also allows the naive solution to pass, but C and JavaScript require an algorithmic solution to avoid timing out. I suspect that the test cases for some languages are significantly different from others, and probably need to have someone go through and bring them all to the same standard. (That is, either naive solutions always work, or all languages require some implementation of an algorithmic solution.)
Edit: Python also allows the naive solution to pass.
timed out ofc...
This certainly did not feel like a 7 kyu, especially with the optimization required for Javascript. I learned alot though, thank-you to the author.
Doesn't Work correctly
c++
Doesn't work correctly HOW?
My Code Correct but Timed Out
I checked your code and it is, unfortunately, too slow. It works well for small numbers, but works very, very sloooowly for larger numbers.
It's a bit of a bad luck, because usually, white kata are meant to have no special performance requirements and should accept also some kinds of non-performant solutions. Unfortunately, this challenge does not follow this pattern. It can be considered more difficult than other 7 kyu kata, especially for newbies.
It works now
It's just a math logic :)
anyway Thx for reply me hahah
Really enjoyed this one. Lots of nice elements to it. Learnt alot from it
Random tests in Haskell only test inputs up to 100. I've made a fork that updates the random inputs to match the description (values up to 500,000)
C: in the random tests, the user function is tested against itself
fork fixing it, also clearing a warning and moving the testing code out of preloaded
Merged.
Are we trying to learn to code or doing a math class? why test giant numbers that require optimizaton of code on a 7 kyu?
You can choose literally every other kata to solve, you do not need to solve math kata if you do not like them :)
But why are JS tests so restrictive? Many other translations don't require any optimizations, and that makes sense for 7kyu.
After a quick scan, I only found C, C++, coffeescript and JS to have some kind of restrictions. The way I see it, either those translations should be softened, or every other translation should be updated, but then shouldn't it be 6 kyu? Nasty situation overall :/
I think that I personally would prefer softening the tests to standards of 7 kyu kata. I think it is reasonable to accept O(n) solutions for this particular kata, as there is many yellows which require performant factorization.
It's unfortunate that the author's intention wasn't fully realized. They were clearly seeking some degree of optimization. However, the issue lies in the fact that ranking inflation was already a widespread practice at that time.
Groovy Translation
Approved
This comment has been hidden.
This comment has been hidden.
OP solved the kata
uh, I don't understand math very well to solve this kata...
Lua translation!
Approved
I can not pass for big Number !!
This comment has been hidden.
i cant pass the big test maybe because my code is slow 😆
Execution Timed Out (12000 ms) anyone same situation as me ? i use for loop and counter++
you need to optimize your algorithm
and it appears that you've already done that, congrats
This comment has been hidden.
This comment has been hidden.
i <= 9- why 9? My guess is this is causing inifinite loop.Try printing value of n at the begining of while loop.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
That's a problem with your code, not a kata issue.
This comment has been hidden.
you guys should remove this kata it broken i tried two solutions one in arrow fuctions the other with for loops (const getDivisorsCnt = (n) => Array.from({ length: n }, (_, i) => n % (i + 1) === 0).filter(Boolean).length; )
(function getDivisorsCnt(n){ let result = 0 for (let i = n; i > 0; i-- ){ if (n % i == 0){ result++ } } return result })
dosent work for either and these are litterally the only way to solve this problem im having the same max buffer problem as everyone else its not a code problem its a kata problem please fix this thank you
This comment has been hidden.
This comment has been hidden.
Your code gives too much output to the console. Try removing
console.logs in your code, then submit it again.This comment has been hidden.
This is an optimization issue. If others are able to pass with that solution (and I wonder how you are able to tell?), then they simply got lucky with random test.
Your approach is doing the most naïve thing possible. I am sure with some thought (or, alternatively, a tiny bit of research), you can come up with something that doesn't try to divide every number up to
n. Implementation-wise, this is very much a 7kyu problem. Solution-wise, it is also 7kyu, even if you can't figure out the correct approach yourself (again, your ability to research does not factor into the difficulty of a challenge).Not an issue.
I was watching this video (after a tiny bit of research) that solved and submitted the same solution successfully: https://www.youtube.com/watch?v=x43VjoEw1FA
I am aware that there are ways to further optimize the solution, so I guess this user may have gotten lucky with the random test. I will keep trying. Thank you for your feedback and insight into this being, in fact, a 7kyu. Since this is a common question / falsely reported issue, it may be worth adding a note to the instructions?
This comment has been hidden.
The JavaScript translation is working fine. The kata has been passed over 18.5K times in that language. Your code is too slow. Not a kata issue.
That's a fixed test, not a random one, random tests go indeed up to 500000.
This comment has been hidden.
I totally agree with this comment. The test is testing a number out of the scope of the function. It does not matter how many people has passed the tests. The tests are wrong. You should change either the description of the funcion or the tests.
This comment has been hidden.
Your code being not fast enough is not a kata issue.
This isn't really a 7 Kyu (It's harder), it's an optimisation problem. So you have to think of a way to cut down on processing (amount of times you loop).
This comment has been hidden.
Yes, this happens sometimes when the code is wrong.
Try running this in your VS Code:
This comment has been hidden.
Yes, you did something wrong, and I tried to show you how to figure out what you did wrong. In your VS code, your code also gives wrong answer if you run it like this:
disregard. I just found out i shouldnt use global var in kata
Just saw your reply. Besides the global var my code was completely correct.
What you first replied with made me more confused... I honestly do appreciate your attempt at help though!
The "besides" part makes a big difference tho!
Oh I am sorry to hear that, because I definitely did not mean to confuse you :) Glad you got it tho!
This comment has been hidden.
You don't need an array to count numbers, don't you?
This comment has been hidden.
Read this: https://docs.codewars.com/training/troubleshooting/#works-but-no and don't use global vars.
This comment has been hidden.
See the sample tests when in doubt.
I had the same difficulty/confusion. The examples indicate that we are to return the number of divisors followed by an array containing each divisor, but the correct answer only included the number of divisors.
Added a note, see if that's clear enough.
I changed the description of the examples. I hope this helps.
This comment has been hidden.
.
This comment has been hidden.
o_O
the swift translation has no sample test cases implemented, it's still the default template that always return true
I've approved your fork fixing this issue. Thank you!
This comment has been hidden.
approved
Lmao. No way this is 7 kyu
This comment has been hidden.
Fixed in this fork: https://www.codewars.com/kumite/62a576c3aa443d6a5509b546?sel=6336a46376c8c84fe34231af
Approved.
This comment has been hidden.
approved
This comment has been hidden.
fixed (increasing range up to 500,000)
This comment has been hidden.
What do you suggest?
This comment has been hidden.
kata hint != kata suggestion
This comment has been hidden.
Don't create an array. With a large number this is very heavy.
TY I'll give this a try
This comment has been hidden.
Not an issue, post your code in spoiler and use
questionlabel. Most likely due to infinite loopThis comment has been hidden.
Do you know what input makes your solution to fail?
https://docs.codewars.com/training/troubleshooting#print-input
Hi hobovsky, the error says undefined should return 1. Sorry I didn't mention that previous.
Yeah, I have made the adjustment to undefined should return 1, accounting for that and the test is still failing with the same error.
undefinedisn't the input, it's what your function returned. You forgot to returnallDivisors. About failing just one test, that wasn't the case, depending on the Node's version you select, you can see your code failed all of them.Thx, Chrono79, oh boy missed that.
This comment has been hidden.
approved
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
n = 1test added to sample & fixed tests forCandJavaGoto include this testThis comment has been hidden.
Removed test with 0 in Java, fixed description.
This comment has been hidden.
OP solved it, closing
This comment has been hidden.
OP solved it, closing
This comment has been hidden.
OP solved it, closing
This comment has been hidden.
This comment has been hidden.
Approved :)
This comment has been hidden.
This comment has been hidden.
This solution gives out all the dividends, but you need their number
Too much tests. my code isn't efficient enough.
This comment has been hidden.
Hi Lorenzo, this is not a kata issue. Please note that there are over 400 solves in C language; if there was such a bug with the first sample test, it would have been discovered long ago. Re-check your code: it returns
0no matter what.Sorry, i'm trying to understand how this platform work and thanks for the advices. I have correct that.
You have to use return instead of printf
yep, already done! thx
Test cases for Go should go up to 500000 as in the Kata description
This comment has been hidden.
This comment has been hidden.
Thank you to reporting.
Fixed.
C translation kumited
'alr approved some time ago'
C# Test Cases do not include squared numbers. Therefore the No 1 Solution is wrong on every squared number.
This comment has been hidden.
Even better is to iterate to sqrt(n)+1. Any number that is a factor has a pair, so you just add 2 for each one you find.
By incresing the Test size you could force those optimizations, I just tried the most simple simple and it worked.
Prolog translation kumited. Much lower input range, but average solution can take from 6 to 8 seconds as is.
no clue what it was asking for as output
What you don't get of this?
The title said find divisors, so i thought oh i should return an array or something to contain all of the divisors
And the description specifies it is the number of divisors and not the divisors themselves what you should return.
Changing the kata name to "Find the number of divisors of a number" doesn't seem to help, or does it?
And the title specifies it is the divisors and not the number of divisors themselves what you should return.
Sorry, but you can't expect to read the title and not the instructions. That's just wrong. The title doesn't need to contain all the description in less than ten words (countless books and movies titles are examples of this). If you have a better title, propose it and maybe it can be changed.
Anyway, I changed the title and the description to
Count the divisors of a numberI hope that's clear enough now.Factor, C++, Dart, Julia, PHP, R, Racket, Reason, and TypeScript translations kumited.
Hi. Sorry it took so long, I don't check codewars veryoften these days. I wanted to approve thses translations, but looks like there were some edits to the kata in the meantime and I need to merge them first. I get an error
Description cannot be approved, recent changes from related record must be merged first.. Anyone here knows how to deal with this? I can't see an option to merge any changes.I forked them and resolved the merge conflicts; please try all my forks.
I managed to approve only one of them - https://www.codewars.com/kumite/5e0a06a58c719600251ab40c?sel=5e0a06a58c719600251ab40c And after approving it I get this message for the rest of them "Description cannot be approved, recent changes from related record must be merged first." I don't know if they don't require one translation at a time, to keep sequential history. No idea.
Can you ples try forking it again but only for TWO langs? We will test how merging translations works here. If I'm able to approve one, but not the other - we will know that we have to do it in this way - you make a fork, I approve it, and so on. Seems super odd, as these forks should be mergable all at once. But I can't really tell how this process work.
It normally works fine, but apparently something weird got changed or something--it shows no merge conflicts (https://github.com/Codewars/codewars.com/issues/19490).
Forked them all again (not changing anything but a whitespace [so it lets me through]), hopefully it works this time.
(Note: if it doesn't work, feel free to fork them yourself and add an empty line somewhere.)
All approved
The description is too brief to clarify how the output returns
Attempted in c++ 14, got this as error message
main.cpp:34:9: error: use of undeclared identifier 'unordered_set' unordered_set s = {1, n}; ^ main.cpp:34:28: error: expected '(' for function-style cast or type construction unordered_set s = {1, n}; ~~~~ ^ main.cpp:38:17: error: use of undeclared identifier 's' s.insert(x); ^ main.cpp:39:17: error: use of undeclared identifier 's' s.insert(n / x); ^ main.cpp:41:16: error: use of undeclared identifier 's' return s.size(); ^ 5 errors generated.
I'm gonna remove C++ translation for now. I don't have time to work on it currently.
Ran into issue when "Attempting" in C++ 14:
main.cpp:34:9: error: use of undeclared identifier 'unordered_set' unordered_set s = {1, n}; ^ main.cpp:34:28: error: expected '(' for function-style cast or type construction unordered_set s = {1, n}; ~~~~ ^ main.cpp:38:17: error: use of undeclared identifier 's' s.insert(x); ^ main.cpp:39:17: error: use of undeclared identifier 's' s.insert(n / x); ^ main.cpp:41:16: error: use of undeclared identifier 's' return s.size(); ^ 5 errors generated.
Issues seem to be outside my code...not sure there's anything I can do about this. Dissapointing but not necessarily surprising.
My advice is to stop feeling dissapointed and fork the translation and fix it if you want.
No random tests in C++, Haskell (only 2)
For Haskell QuickCheck tests the number of test runs is defined in the config, it's 100 by default. So there're 2 times 100 random test checks here.
That was absolutely unclear for me.
So only C++ lacks random tests.
Submitted randomized testing for C++. Please review.
https://www.codewars.com/kumite/593cf084edf0d31e39000032?sel=5b63c972146a28fe7a000017
Submitted randomized tests for C++. Please review and approve.
C++ translation was removed in the meantime
I've realized because of that kata that i have to study algorithm books ;p
:)
This Kata proves (which is already proven) that C++ is faster than C#. My code doesn't fit into 1200ms for C#, but perfectly fits in C++. And even not optimized pass for each number fits too. Sad, but I don't know how to make my code faster for C#... Or maybe it is just server problems..
It proves nothing. The tests may be different and there's a great number of factors like environment, compiler options etc.
Yes, sure. Always forget to add smiles to my sarcasm %) Didn't check other solutions, but I bet that I had server issues.
The C# version has performance tests.
Hi, I added a C# translation, please review and approve.
Great Kata but I suggest you add some random tests... ^^
Added random tests to python too.
Fixed
Ruby translation, please check and approve :-)
Added C++ translation! https://www.codewars.com/kumite/593cf084edf0d31e39000032
It says I both
Passed: 1andFailed:1. I know I didn't fail because I was able to deliver the value that was needed, but it said I still failed. Is there something wrong I am doing?This comment has been hidden.
For each divisor there is an inverse, i.e 52 and 25. For 11, it is 111 and 111. Your for loop stops at half of the number so it doesn't include the inverse.
Problem statement says that integer n is positive, but there is a test, where n == 0
public long numberOfDivisors(int n) n is int, but method returns long.
Why is the below not working? public class FindDivisor {
public long numberOfDivisors(int n) { // TODO please write your code below this comment int divisors=0; for (int x=1; x<= n/2; x++) { if (n%x==0) divisors++; }
} }
Test Cases: Test.assert_equals(divisors(4), 3) Test.assert_equals(divisors(5), 2) Test.assert_equals(divisors(12), 6) Test.assert_equals(divisors(30), 8)
Yet this is generating Java errors when I Run Tests.
java.text.ParseException: Failed to parse java class in code: Test.assert_equals(divisors(4), 3) Test.assert_equals(divisors(5), 2) Test.assert_equals(divisors(12), 6) Test.assert_equals(divisors(30), 8) at codewars.runners.java$class_name.invoke(java.clj:18) at codewars.runners.java$fn__572.invoke(java.clj:107) at clojure.lang.MultiFn.invoke(MultiFn.java:227) at codewars.runners$run.invoke(runners.clj:22) at codewars.core$_main$fn__634.invoke(core.clj:40) at clojure.lang.AFn.call(AFn.java:18) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:745)
Your tests refer to methods that don't exist. For example, what is divisors? Read the test reference to see how to create the unit tests and test the class. http://www.codewars.com/docs/java-test-reference
While my code is running, i do not yet understand how the testcases work. I used the following, only got a cryptic error-message however. Can anybody tell me how to do it properly?
var input = 4; var expectedResult = 3; var result = numberOfDivisors(input); Test.expect(result === expectedResult);
Found the solution in a different Kata:
import org.junit.Test; import static org.junit.Assert.assertEquals;
public class SolutionTest { @Test public void test() { //when inputting 4, the expected solution is 3 assertEquals(3, new Solution().solution(4)); }
}
Description incomplete, it says "Example: " but then the description ends there.
I agree, I don't understand what we are supposed to do here...
You have to "Find the number of divisors of a positive integer n."
Missing example not reproducible; issue does not specify which language.
Closing.
This comment has been hidden.
Less than what? :-)
You can stop at sqrt(n)
This comment has been hidden.
fixed
Here are test cases. I hope it will reduce the opportunity to troubleshoot for any new members:
Test.assert_equals(divisors(4), 3) Test.assert_equals(divisors(5), 2) Test.assert_equals(divisors(12), 6) Test.assert_equals(divisors(30), 8)
added, thank you
I found this problem to be more or less a test on time.
Where the most popular algorithm is neat on one line, I wouldn't ever user in production code unless I'm sure the values are less than 10,000. The code I made is O(log_2 n)
Then again, I work in iOS and pc gaming applications, so thinking of quick to execute code is something I gotta do.
Your code fails for 143 = 13 * 11, or other numbers which have prime factors other than 2,3,5 and 7
Having some pre-set tests would be helpful.
No language specified. Closing.
Nice Kata for this Kyu.
This would become a lot harder if larger test numbers were added, such that a brute force solution would time out. Maybe in a lower Kyu?
Edit: Also, clicking "View solution" under a comment seems to mess up the formatting (In case you're wondering why my solution looks the way it does): It uses a different tablength than otherwise. I used tabs out of habit because I'm used to them being translated to spaces.
My prime-factorization based solution became faster at n = 10000
Averages of 250 testcases Random numbers up to 10^1: Prime factors: 0.000 s, naive = 0.000 s Random numbers up to 10^2: Prime factors: 0.001 s, naive = 0.001 s Random numbers up to 10^3: Prime factors: 0.007 s, naive = 0.004 s Random numbers up to 10^4: Prime factors: 0.044 s, naive = 0.044 s Random numbers up to 10^5: Prime factors: 0.289 s, naive = 0.456 s Random numbers up to 10^6: Prime factors: 3.563 s, naive = 5.182 s Random numbers up to 10^7: Prime factors: 26.995 s, naive = 56.739 s
Can't be changed due to amount of solves && that one would be a performance version which already exists!
The latter issue should be fixed after 7 years
This comment has been hidden.
I think where you're going wrong is that your
forloop capsibyn.lengthrather than the value ofn.Also your short-if should probably have a false condition with
:This comment has been hidden.
Ok, its the size of the array generated.
Are any function similar to Python "xrange" for Javascript?
Yes. This is it. Generating a huge range this way just isn't going to work, apparently. The
.slice()doesn't help, but I don't know if that's the actual problem.would be more understandable, and more efficient because of no
.slice(), than your code. I had to do some very careful reading to understand how that worked. It's ingenious, but not very flexible or maintainable.This one's going to take a little bit of research since my solution's timing out.
I would say direclty what is expected output. It is misleading that there is sequence of dividers given and the amount of dividers. Firstly, I returned all the values that are dividers. Generally, I would add "Return value is expected to be integer representing number of dividers..." or sth similar to that.
Isn't 'Find the number of divisors of n.' obvious enought? I think I'll wait for some more feedback, from other warriors.
An request to everyone - please let me know if description need further clarification
I think you can edit the example - so it doesn't look like output data should be '1, 2, 4.....'. When you read description briefly - like in my case - this is causing confusion.
Sometimes unknown error occured
Thanks for all feedback. I will update description and test cases as soon as possible :)
The problem description should specify that n > 0 (that n is an integer is already implied), and there should perhaps be negative tests if n is allowed to be 0 or negative.
I changed the description.
Also, square numbers seem to be a good edge case, as they will have an odd number of factors rather than even, so it would be good to add some explicitly to the tests.
I added such test cases.
Marking resolved.
Awesome.
Some solutions (mine included) would fail for n=1. You should add that test case.
Will do, thx
I added test cases for n==1. Thx.
Nicely done. Strangely, there was a "random test case" that my code failed, but because the message wasn't very useful, I couldn't debug it. Could you generate the test messages for each test, too? This would be really helpful.
I will add the number to message, ok?
That'd be perfect. Thanks!
I changed the message. Is it ok now?
Yeah--spot on! ;P