6 kyu
Count the divisible numbers
1,436 of 3,616joh_pot
Loading description...
Fundamentals
Algorithms
View
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.
It's not algorithm problem, it's pure math. Suggest to remove tag
Algorithms
, add tagMathematics
and reduce difficulty level to7 kyu
.This kata looked easy at first but I did not realize a solution faster than linear time was required. After writing out a few test cases and all the possible combinations that returns the same answer, I was finally able to connect the dots for a solution in constant time.
I'm either 1 too high with half the test cases in one "solution" or 1 too low in half the cases in another, are the test cases alright??
python new test framework is required. updated in this fork
Approved
I have no idea how to resolve with no timeout problems, I'm using a linear aproach...
Linear is worse then that.
Yeah, i understand that linear is worse than log, but i do not know how to include logaritmics in this solution...
Math is your best friend, it is explained in your comments, you just have to convert them into valid code !! ^^
This comment has been hidden.
Sorry, but that is a problem with your code, not a kata issue. Try with another algorithm:
D translation
approved
This comment has been hidden.
range(x, y + 1)
has too many items and they cannot fit into a list.The inputs are HUGE. If you could solve this by trying to divide every number in the given range, this would be an 8kyu kata.
Go translation
approved by someone
Rust translation.
Approved!
C:
k
is not random in random tests.fixed, thanks
All of the comments about how this is a "maths" problem rather than a "coding" problem remind me of the classic S. Harris cartoon:
I'm on the verge of a major breakthrough
This comment has been hidden.
nevermind i got it
OP solved it, closing
I think there may be an error in one of the ruby examples? I think (11,345,17) should yeild 19 no?
(20)[17,34,51,68,85,102,119,136,153,170,187,204,221,238,255,272,289,306,323,340]
interesting..
This Kata is amazing. I have decided the kate for three attempts. I wrote five or six solutions, but they didn't work. My result has 10 string on finish. It is little, I thought, but after I saw a solution as 1 return and all. Wow! It is a easy kate and a easy decide. And I have decided now her:)
COBOL translation.
Approved
COBOL translation kumited.
Unpublished, waiting for the new COBOL tests framework.
Ruby 3.0 should be enabled, see this to learn how to do it
Please organize the structure of test fixture as following (although it has been mentioned in the attached link, I'm repeated here again)
done
it got me trying like 2 hours to get de constant time one, good challenge
This comment has been hidden.
A lot of un-initialized variable in your code, also code after
return
statement will not be executed. There is also issue in scoping (functional vs global scopes)I've read the discussions and found out that i need a different approach other than using the loops because of the time limit. Can anyone suggest how to go about it? thanks :)
one test case is flawed
there a no multiples of 7 between 0 and 1
Are you sure ?
add tests
x -2 y 2 k 2 , 3 x -1 y 1 k 2 , 1
Prolog translation kumited.
This comment has been hidden.
After solving the prob, when clicked on 'Run Sample Test' gives attempt successfull, but when clicked on 'Attempt' gives error as 'Execution Timed Out (12000 ms)'! Tried this prob offline with various eg and it works fine. Pls looks into this issue!!
Not an issue. Your code is too slow.
There is a faster way to solve this without checking every number.
Nope. I tried two different programs. Gives the same issue. Also i checked my programs execution time for single iteration. Its '0.0009989738464355469 seconds'! So even if your server tried for 100 different itterations, it still won't cross 1/10th of a second. Also I am not the only person getting errors.. so pls resolve this issue!!
Run
divisible_count(101,9999999999999999999999999999999999999999999,11)
Tell me how long that takes.
wow...o.O...do you hav a way of getting that iteration in less than 12s..?? pls share..
Hint: Don't use loops, use maths instead :)
Ok.. saw the attempts now. Din't expect the iterations values to be this long. Guess the code needs to be more efficient. Thanks for replying(and for the hint)!!
This comment has been hidden.
No, it's a problem with your solution, using loops won't work.
so the solution isn't wrong, it just isn't efficient enough for these tests?
Well, depends on what you consider being right or wrong, for the values used in the tests it's not efficient enough.
yea that's okay. I'm going to have to do a bit of thinking. I'll maybe leave it and come back to it later. Thanks for the reply
Can someone explain to me how,
x = 0 y = 1 k = 7
should expect 1?
python!
0 / 7 == 0
or0 mod 7 == 0
Any language!
;)
Ah yeah! totally forgot about that. I am failing 2 tests: 0 1 7 20 20 2
any tips?
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Yes. Read this
Because some inputs are HUGE numbers, the tests can't complete in time. You should look for more general algorithm without a loop, or a formula.
This comment has been hidden.
the solution can't be "off sometimes" due to rounding inconsistencies because it doesn't use
round()
orfloat
ordouble
. i suggest your code should similarly be restricted to use only the single data typeunsigned long long
for all calculations.Negative numbers are currently allowed, but there are no such tests.
I'd say add to the description that the numbers are positive, just to not render all current solutions invalid.
There is one more serious issue discovered while translating for NASM. Some implementations including first of mine do not check for
x
overflowing undery
. Look at the case 've just added to the C translation: cr_assert_eq(divisible_count( 64, 73, 27 ), 0 ); /* case to check for correct overflow implementations */Do not know what about the other languages... But this case or similar should be added!
awesome catch, thanks
edit: self-catch (chuckle)
This comment has been hidden.
Finding an algorithm that works with a certain input range/value is programming work. Is math involved in that? Yes. Should you google for that? Not necessarily.
Code challenges are a test, on a test you can't google anything. Additionally, on a math test they tend to give you formulas for things you will encounter. In this case if the formula is provided you are still testing their ability to make it work with the limits placed, and removing the requirement to memorize formulas as I'm sure even senior programmers don't have all math formulas memorized.
Yeah, we should ban Google, burn all the books and research papers, delete all software libraries, and do everything on our own because that's obviously how software development works. Using the Internet is not allowed during exams because it can be used for cheating (searching for answers on the Internet, asking other people for help etc.), and it's impossible to prevent the latter without banning the former. And if you haven't noticed, this is not an exam.
Sounds like you don't know basic math, but whatever.
You seem fairly outraged over a trivial comment, you should probably take a breather. This is a place of learning and discussing, not toxicity.
When I solved in Python 5 months ago, I also hit the wall with the tests, at first. Unaware of any possible formula and without google I just persisted and came up with my own solution (that actually did use some looping). I started self-teaching programming a couple of years ago & have just the most basic maths education, but I still enjoyed this kind of challenge.
rowcased, that's great that you overcame it. I tried a lot of different iterable solutions because I assumed there was one that was more optimized and that is what I was missing. I know more of what O(1) implies now. I guess college level calculus is basic math?
calculus? lol, I never even took trigonometry. I guess I've just learned how to visualize numerical relationships and hack away with various tools like modulus and whatever. codewars has been my higher maths education, ;)
When I studied calculus I had to deal with limits, derivatives, integrals, and you're telling me "dividing 2 numbers" is as advanced. Either you've never studied math after school, or American education is even a bigger joke than I've heard :trollface:
Codewars is My Math Tutor
+2
Anybody Else To Count Up?)
This is not a 6kyu problem with the optimization requirements being imposed.
Please specify in the Details section that you are forced to be O(1) and that loop based solutions will not work.
Without the
O(1)
it would be a 7 kyu Kata. Edit: The Best-Practice solution has 33 characters + function declaration and is no code golfing, so 6 kyu is more than appropriate.Current 6 kyu kata level description:
The algorithm that works isn't complex enough to rank it higher (and rank can't be changed anyway). I agree it should be mentioned loop based solutions won't work or something like that to avoid frustration.
These math problems, as opposed to programming problems which is the reason people come here, give the wrong impression that programming requires good math knowledge, while in practice it's not like that.
Actually math is just a tool to improve performance in programming. I agree that 90% of the time you will just use the work of the people before you who did the math, but as programmers we are problem solvers per definition. If you keep programming and challenging yourself there will come a day where there is no precut algorithm and nothing you can cobble together from the existing knowledge is efficient enough. On that day you too will contribute by doing math and creating what is needed so those learning programming after you will have even less reasons to understand math to program. Programming is math - but in a cool way :D
@slacle, well, it depends on how you want to take it. Nobody forces you to solve this particular problem, which may require some math, but at the same time, you are free to ask and read questions and answers (this is how I found out I need some math formula). Once you find it out, you have to search for the formula, which is also a programmer skill.
give the wrong impression that programming requires good math knowledge
Searching and applying a simple math formula is notgood math knowledge
.Java translation
This comment has been hidden.
Loop based solutions won't work, read the posts below.
Which posts below? I'm not finding one regarding this issue
Luminux's post contains a discussion talking about it. There is some other one but it's marked as having spoiler content because it has code in it.
I passed all the test.. but it seems that JS has error during the attempt, like -> FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory <-
AND, I don't quite understand this error: [1:0x56268f39e000] 2775 ms: Mark-sweep 580.4 (592.2) -> 580.4 (592.2) MB, 95.0 / 0.0 ms allocation failure GC in old space requested
please fix this.. thank you
it would seem you are using too much memory in processing the data (
JavaScript heap out of memory
). you need to find a more efficient approachThis comment has been hidden.
you may have passed all the Sample Cases, but the Fixed and Random tests have larger numbers. with the error message as your guide, ask yourself; why a range error? which array is affected? what's the invalid length value? which part of my code is causing that? maybe use some console.log() and hunt it down and fix it
Please, NASM Translation
Done
Hi I have found a solution that works for all basic cases and the cases I have used in my terminal in Python. I have been using a list comprehension and get a memory error on the full set of test cases, presumably I need to optimize my function. I have read that I could use generators though I don't have an idea of how to set up a generator such that it optimizes memory and can still count all of the occurrences of those divisibly by k. Any help?
Nice, but IMHO too easy for 6 kyu.
This comment has been hidden.
the numbers are so large you don't have time to simply iterate through them completely => you need a different approach
Ruby translation kumited -- please check and approve.
How exactly does 1 go into 7, one time?
You're wrong if the test is
Test.assertEquals(divisibleCount(0,1,7),1);
0 is divisible by any number (except 0) and that's the number being counted, not 1.I passed all the test.. but it seems that JS has error during the attempt, like -> FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory <-
AND, I don't quite understand this error: [1:0x56268f39e000] 2775 ms: Mark-sweep 580.4 (592.2) -> 580.4 (592.2) MB, 95.0 / 0.0 ms allocation failure GC in old space requested
please fix this.. thank you
Please post your code and tick the box
Mark as having spoiler content
.This comment has been hidden.
Hi Dimas_Day, unfortunately you have not passed all the tests, just the sample tests. The Fixed and random tests contain larger numbers, so you're getting a
JavaScript heap out of memory
error because you're trying to use more heap than is there to use to calculate from them. The javascript tests do not need to be fixed, you need to optimize your code to use less memory... (also make sure it's optimized for time) Good luck!C translation kumited
thanks!
This comment has been hidden.
Numbers go up to
Number.MAX_SAFE_INTEGER
, it'll take the entire day to loop to that. Try another approach, not a kata issue.I see, I wasn't aware of that. Just seemed buggy.
As several people pointed out the basic tests are plain wrong! I seriously question how this mess of a kata managed to get 91% approval from the community! Wasted serious amount of time on a author mistake . . .
Edit: After looking at the responses regarding issues in other katas from this author it seems he is truly incompetent since he refuses to solve the clear issues. It seems his idea of contribution to this website is to force the users to waste time on trivial bullshit!
wow, very anger
it says you authored 0 kata (at least using that account) which means this author still needs you to show how it is done ;)
Hi Luminux. Can you tell me what language you were using to complete the kata? This kata is quite old and I'm not very active on this site anymore, at least when it comes to authoring katas. Before a kata can go live, it is in beta status. When enough users have completed it and ranked it, it can be approved by a power user. There's quite a bit of back and forthing before it is a ranked kata. Hopefully by then, the bulk of issues would have been sorted out, so things like basic tests would have tested thoroughly, not just by me, but the hundreds of other users that have completed it, so I find it unexpected when a user raises an issue for basic tests. This leads me to believe that my description is most likely not conveying what I need to be done or what I have seen countless times, users skim over the description and basic tests and then implement the wrong thing, thus leading to their frustration and then lashing out. It would be great if you could tell me what test is wrong and why you think it is wrong so I can understand where you're coming from. You need to understand that everyone that authors a kata does this for the community and no one here gets paid so it is very disappointing to me when I see behaviour such as yours. Please answer the questions I have asked you so I can have a look otherwise I'm closing this issue.
First of all i'm sorry for my excessive behavior towards you! I guess i must have been having a rough day... (not that it's any excuse)
Regarding the issue at hand, I was attempting it in C#!
Thanks Luminux. I have updated the test cases and reference solution to what @Bouchert below has suggested. I'm not the author of the C# kata, I only created the javascript version, so I wasn't aware of the float rounding issues.
Just my thoughts, but if your going to have random test with numbers so large you are intentionally trying to fail solutions on the basis of a time then you should mention in the description that is your purpose. There are many solutions that work to solve this issue, but you are intentionally seeking only one math solution, and again intentionally omitting a programmatic one.
Hi psmilliorn. It is very clear in the basic tests that everyone can see that a loop based solution will not work. You don't even need special maths to pass this, just some tinkering around with basic operators. I have no purpose to fail solutions, there is only a kata with very visible test cases that need to be passed, nothing more. This is not a "performance" kata, there is no special data structure of complex algorithm needed. In real life, if you had to implement something like this for your job, would you or your boss be satisfied with a solution that runs minutes or completes in milliseconds?
I think adding a note about it won't hurt anyone, like "your function will be tested with big numbers" or whatever you think is ok.
There´s errors on the basic tests, just fix this. Spent hours thinking about this until I had to unlock solutions and notice is not my mistake.
Fixed.
Python translation
Please approve.
There seems to be an error for the following BasicTest for c#: 101, 9223372036854775806, 11 Expected: 838488366986797815 But was: 838488366986797791
since 9223372036854775806 / 11 = 838488366986797800 I can't see how the expected value is higher than it
I have the same issue.
Fixed. See @Bouchert below's comment. Your answer will still be wrong after the fix.
This comment has been hidden.
Fixed
C#-Translation kumited.
https://www.codewars.com/kumite/57a098a5bb9944235a000169
Please check and approve!
Thanks mate. Approved.
This comment has been hidden.
Nice kata! Thanx!
Hey, my code works but it won't pass because: 'FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory' How do I get around this?
Ive had the same issue, was a solution ever found?
Your code must be causing stack overflows. It is running out of memory.
This comment has been hidden.
I'm testing with large numbers. Your own solution imposes the time limit.
Nice!
Why is my solution taking longer than 6000ms to complete? I only used a for loop and an if statement inside.
It should be o(1). For loop wont cut it.
what is o(1)?
"An algorithm operates on input, and the size of that input usually determines its running time. Big O notation is used to denote the growth rate of an algorithm’s execution time based on the amount of input. For example - the running time of an O(n) algorithm increases linearly as the input size n grows.[3] The running time of an O(nˆ2) algorithm grows quadratically. If it is possible to establish a constant upper bound on the running time of an algorithm, it is considered to be O(1) (one might say it runs in “constant time”). That is, an O(1) algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.[4]" https://en.wikipedia.org/wiki/O(1)_scheduler
In other words it means the kata is boring and you have to solve it with Math and not programming stuff.
"Boring" is a bit harsh. I think the kata rating is too high, but after doing the math it's somewhat interesting to find a "small" solution to this one.
Great kata!
Interesting Kata! Seems so easy at first glance, that is eventually straight way to make overcomplicated solution. Thanks!
This comment has been hidden.
10%1 == 0; //1 9%1 == 0; //2 8%1 == 0; //3 7%1 == 0; //4 6%1 == 0; //5 5%1 == 0; //6 4%1 == 0; //7 3%1 == 0; //8 2%1 == 0; //9 1%1 == 0; //10 0%1 == 0; //11 The test is correct. I don't see your issue. How can it possibly be 12?
Sorry the error is mine.