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

    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

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