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.
The idea is that no number from the interval (n/2, n) will ever be a divisor of n.
Thank you for the explanations. I think that I am getting a bit closer to understand all of this.
You are almost correct, however, we need to be careful about how we simplify the equations. The time complexity of making a single slice is (omikron) O(n). Making two of them, theoretically has a time complexity of O(n + n = 2n). Note that we are adding, not multiplying. Since 2 is a constant, we can omit counting it. (In other words, the functions n and 2n grow at the same rate.) Just making the slices has therefore a time complexity of O(n).
This happens for every element, so we then multiply by n and get O(n²).
Trying to understand the complexity here, am I right to think this is quadriatic due to fact that each slice operation time complexity is (omega) O(k). So as we doing two of them it is O(k) * 2 = O(k^2). Then there is iteration cost which is O(n). Not sure if this can be seen as k elements in the list as well therefore with slicing together ending in worst case scenario complexity of O(k^2) * k or O(k^3). Does this make any sense? :-)
Souce of info: https://wiki.python.org/moin/TimeComplexity
This comment is hidden because it contains spoiler information about the solution
Yes. The "else: pass" in your code can be omitted without any issues.
I'm not sure if I understood you correctly, but this is, in fact, O(n^2) too.
While one-liners look smart and cool, this is not really good practice. For every element of the list we make a slice (so in worst case, we go over all of its elements again) and then call the count method on the slice (by which we go over all of the elements of the slice).
In the end, what could be done with just one iteration over the list, is done with numerous redundant iterations.
This comment is hidden because it contains spoiler information about the solution
Also, looking up if an element is in a set happens in a constant time, i. e., it always takes the same amount of time, regardless of the size of the set. Looking up if an element is in a list happens in a linear time, i. e. in the worst case, it has to go over all the elements of the list, and here, it would be very inefficient since we have to search the data structures repeatedly.
In one line but for what price... The code is terribly inefficient. Your solution has more lines but it is faster and cleaner.
Absolutely not best practice. Number of instances of one character is something you can very easily do with just one iteration over the string. This code goes over the entire string for each character unnecessarily.
I really wish newbies shifted their efforts from making "fancy" one-liners with terrible efficiency to writing actual respectable pieces of code. And I also wish people stopped upvoting codes like these as "Clever" or even "Best Practices".
It's a possibility and a smart one, but absolutely not "Best practice". In the worst case, the slice has to go over all the elements of the array and since it happens in a loop, the function ends up being quadratic (= time needed for its execution is proportional to len(arr)^2). However, this could be solved with linear complexity (= time needed for the execution is proportional to just len(arr)).