Retired
The nth smallest integer (retired)
223 of 868user4912975
Loading description...
Fundamentals
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.
This kata is a subject to deduplication process here: https://github.com/codewars/content-issues/issues/132.
Please join the discussion to help us identify duplicate kata and retire them.
Retired.
This comment has been hidden.
Ruby 3.0 should be enabled, read 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)
Kata retired.
Please review Perl translation: https://www.codewars.com/kumite/602442c047c8ed002169bbf2?sel=602442c047c8ed002169bbf2
mine is timed out at 12000 ms with small knowledge I have at the moment it needs to be sorted with O(log n) which i do not know how to execute Will come back to it later
This comment has been hidden.
This is honestly impossible. Even when you use solutions of people who were able to complete it, I still get timeout errors. What are we supposed to do?
Something must have changed in the CW runner at some point. Decreased the number of big tests to fit within the given time limit.
Thank you. I resubmitted my solution and was able to solve it in around 10.2 seconds.
(Meanwhile?) impossible to solve in Python:
After struggling for two days (high & low level) and always running into the same timeout, I finally gave up and decided to check on the commited solutions.
But surprise: re-commiting those resulted in the 12k ms timeout, as well. Not sure whether I'm glad or depressed..
TL;DR The timeout thing needs a fix (a guess: too many oversized tests)
Farekkusu just fixed this problem. It should work now.
This Kata is too low leveled. Using a heap, quickselect, etc seem to fail. I don't expect people without decent algorithmic competence to pass this without massive effort expenditure due to the size of the test cases.
This comment has been hidden.
This kata is impossible to complete in javascript. There are too many test cases and therefore the kata won't complete. Please fix.
Your code is too slow.
I'm not sure. Even if I cut the code, and leave it at 'return n', it's still 700ms. Can you please look into it?
What's the problem with 700ms? That leaves you with 11300ms to spare, so your code can even be 15 times slower than the reference solution.
So then code speed isn't the issue because the solution doesn't reach anywhere near that limit
The time spent by a blank submit is not the time it takes for the reference solution to run the tests because you also have to take account for the time to generate random test cases. When the test case size is large this is actually a very heavy operation (at least O(n)).
But in any case, since the kata needs to be published with a working author solution it can be passed. "I can't pass the tests" is not a valid ground for an issue, but instead a question ;-)
What I mean is that the execution does not stop because of time out at making the 'attempt'. I'm assuming something is broken on the grounds that it works fine in other environments.
And what is the "other environment"? ;-) When you raise an issue you need to give the details, or how do you expect others to look into it? We can't read your mind.
I'm not sure how it will help you if I type the name of some IDE into here. Let's just end this discussion, it has clearly derailed from the original post.
Haskell : https://www.codewars.com/kumite/5b74e66bc74d652bec000013?sel=5b74e66bc74d652bec000013
In Python tests, even a normal code such as 'pass', takes nearly 9550ms. Please take care of this problem
List generation takes lots of time. Submitting
passtakes 9 seconds, while submitting an actual solution takes the same 9 sec. Also, it's not critical.( JS, possibly others )
Needs a fixed test expecting a return value of
0.In the JS version, it says to return
-1if the nth small integer doesn't exist, but in the sample tests it's tested againstnull.The return value for JS was not specified in the description. Apart from that, if one language requires to return
None/nil, most often its equivalent is required in other languages as well.This comment has been hidden.
You could try not reinventing the wheel. In my case, this approach passed the tests easily.
!
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Crystal available.
JavaScript translation ready for approval ;)
.
Ruby translation kumited -- please check and approve!
"fun" fact: ruby is much faster than python -- I added twice as many huge tests, using 6 times the range of python, and it still fits :-)
Seems fine, approved :)
Thanks!
Updated Python translation kumited -- please check and approve!
Approved.
I did marginal checking, cause I don't know Python. If any solver sees issues, please post them.
This comment has been hidden.
I don't think there is any better approach: you need to traverse the list once, in order to make sure you have all elements and drop the duplicates. Then you will need to sort them somehow, in order to find the nth one. There is nothing you can skip...
Selecting the nth element of a list can be done in linear time.
Please elaborate
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
I tried to do it in Θ(n) :/
As far as I know, the Θ(n) solution has a very big constant. I'm not entirely sure how big it is but it may very well not be faster for any number of elements that can be tested on Codewars.
Well, after I read in description, that efficiency is important, I first thought of this. If it had not worked, I would have tried introselect :D
what do you think if you use "nth integer" instead of "nth smallest integer" because when solving it made me think to sort the vector in descending order and remove the recurring integers and then return nth integer if it exist else -1. But then it was the examples that brought me to the actual track.
I guess the phrase 'smallest integer' implies that the vector has to be sorted in ascending order. Also, the kata description clearly states that only unique elements are to be considered.
Also, please upvote if you liked the kata.
ninsmallshould better bestd::size_t.std::vector<long>by value is in no way focusing on efficiency.const std::vector<long>&would be better.static.The fact that only distinct elements are considered when calculating the nth smallest element needs to be mentioned.
Updated description