Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
yeah no you have to implement your own
This solution has O(n) runtime over the size n of the input, which is good. It still needs a second pass over (part of) the input, though, which could mean all of the input in the worst case (e.g. when there are no non-repeating characters or the first one occurs late in the input). If you're interested in a solution that does not need a second pass through the input, take a look at my solution.
+1 for reminding me of the extremely useful
collections.Counter
! Surely I would have implemented the counting myself using a regulardict
if I had opted for it in my solution.Seems like your N's is to small to see benefits from Counter. Your solution is O(n^2), so for large N, your solution will be much slower than op's solution (wich is O(n))
This comment is hidden because it contains spoiler information about the solution
In my benchmark function with Counter was much slower (like 10 time slower) then function with str.count. str.count run N times only if first non-repeating char is last char of string. And str.count itself has O(N) only in worst case
Nice
Fails for (1001)^2
This comment is hidden because it contains spoiler information about the solution
I really do need to work on my knowledge of the prelude functions. I tend to not rely enough on them.
Thanks for taking the time to answer - you've got a good point, I didn't consider that. The difference is going to be well worth the import.
If you count for each iteration of your loop, your algorithm is
O(N^2)
whereN
is the length of the input string. Using a counter makes one pass over the entire string, then gives you constant time lookups for the loop. You end up usingO(N)
time and space for this solution.Just as an aside - if you were to try to build the counter by using repeated calls to
str.count
, you would be incurring a quadratic time penalty, because you'd have to callstr.count
for each letter in the input.Is there any particular reason to use Counter over string.count() here?
Description added.
I don't know why I cannot edit the example test cases after re-publishing several times. You need to calculate all primes less than 3 million. That is what P[i] <= 3000000 for all i means.
Loading more items...