Ad
  • Default User Avatar

    The idea is that no number from the interval (n/2, n) will ever be a divisor of n.

  • Default User Avatar

    Thank you for the explanations. I think that I am getting a bit closer to understand all of this.

  • Default User Avatar

    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²).

  • Default User Avatar

    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

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    Yes. The "else: pass" in your code can be omitted without any issues.

  • Default User Avatar

    I'm not sure if I understood you correctly, but this is, in fact, O(n^2) too.

  • Default User Avatar

    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.

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    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.

  • Default User Avatar

    In one line but for what price... The code is terribly inefficient. Your solution has more lines but it is faster and cleaner.

  • Default User Avatar

    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".

  • Default User Avatar

    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)).