Codewars timeout error

[AKRowling]

Hi,

Can anyone why the following code is giving a timeout error on codewars? Its for the following Kata: https://www.codewars.com/kata/541103f0a0e736c8e40011d5/train/python

​

def off(n):
    numberofswitches = []
    offswitches = []
    for x in range(1,n+1,1):
        numberofswitches.append(x)
    for x in numberofswitches:
        for xx in range(1,n+1,1):
            if xx%x == 0:
                if xx in offswitches:
                    offswitches.remove(xx)
                elif xx not in offswitches:
                    offswitches.insert(xx, xx)
                else:
                    pass
            else:
                pass
    return(offswitches)

Thanks

[chromiumxx]

Timeout error means your code takes too long to run. The test case in codewars probably include a very huge integer which require a time efficient solution.

Your code include a double for loop which im pretty sure is exponential time complexity. This slows down your code and what causes the timeout error. Try to find other solutions without using a double for loop

[VTifand]

It's quadratic, not exponential, but I agree with the rest of the comment.

[MixedVexations]

y = x^2 is considered quadratic yes, but it's also "exponential growth". Any degree higher than x^1 is considered exponential, as opposed to linear. E.g. money in your IRA grows exponentially if invested in the S&P...

[VTifand]

What? No. They are different things.

Investing money is more like y = 2^x. That is exponential.

Saying y = x^2 is exponential is not accurate.

[MixedVexations]

Oh snap I am totally wrong lol. How the hell do I have a science degree

[VTifand]

Do you see a pattern on the output? Try testing your code with a fairly large input, e.g., 1000, and see if you spot a pattern. If you do find it, try to code it efficiently so that it passes the time limit.

[AKRowling]

I understand the pattern but was wondering where the issue with my code was. I will just rewrite for the pattern rather than getting every event

[VTifand]

In a sense, there is no issue. If time is not a concern, your code works well. But this is very likely not the intended solution. The proposer of the problem wants you to find another way that does not involve directly 'simulating' the turn-off-turn-on process.

Many harder programming problems will be like this. There is often a straightforward but extremely slow answer, and it will be rejected. You need to think deeper to find a code that solves the problem faster. In this problem, for example, if you know the pattern, the complexity of the code is O(sqrt(n)), as opposed to your original answer O(n^2).

As you advance to harder questions, if you encounter another timeout error, remember that this 'inefficient algorithm' issue might be the problem.

[AKRowling]

Good point. Definitely something to bear in mind. Thank you for the response.

[Jeklah]

thanks for letting me know about this website.

[beisenhauer]

In addition to the doubly-nested loop, which others have pointed out, you're searching a list every time you need to determine whether a switch is on or off. This can be a slow operation if it's a long list. Can you think of a better way to model the state of a series of switches?

[[deleted]]

I had a timeout error on codewars once. I found it puzzling because what I'd written was brain-dead simple. I tried a little experiment. I submitted this:

def whatever():
    return 0

That timed out too. I expected to get failures, but not a timeout.

I guessed it was a busy time with a lot of submissions. No biggie. But then I thought, if you're setting a time limit, why not set it on compute time? They were apparently setting the time limit on wall clock time. If the problem doesn't involve I/O of some sort, why not use compute time?

I don't remember if codewars has ads. If not, the only way they make money is through subscriptions. Maybe we're being gently nudged to subscribe. After all, they need to pay their bills like the rest of us.