O(N sqrt(N)) will TLE in Python?

  • 0

    I tried some ways in Python in O(N sqrt(N)) and all of them are TLE.

    Does anyone get Accepted in Python using O(N sqrt(N)) algorithm?

  • 0

    me too. And my code is like.

    class Solution(object):
        def numSquares(self, n):
            :type n: int
            :rtype: int
            # Use DP with iterative way
            # dp[i] to store the min number to sum to i
            # init dp
            dp = [0 for x in xrange(n+1)]
            for i in xrange(1, n+1):
                root = int(math.sqrt(i))
                if root**2 == i:
                    dp[i] = 1 # perfect square
                    minValue = float('inf')
                    for rt in xrange(root, i//2, -1):
                        minValue = min(dp[rt**2] + dp[i-rt**2], minValue)
                    dp[i] = minValue
            return dp[-1]

    Any suggestions for speed up?

  • 0

    I think there are some mistake in python's time limit setting.
    I also try a lot of ways to speed up my code. But these modification will increase memory cost and get TLE again.
    In my opinion, the only way to pass this problem using python is Fermat's theorem. But I don't understand it, so I use c++ version of my code to pass this problem.

  • 2

    Well, here's even an accepted O(N2) solution!

    def numSquares(self, n):
        squares = [i*i for i in range(int(n**0.5 + 1))]
        for a in squares:
            for b in squares:
                for c in squares:
                    for d in squares:
                        if a+b+c+d == n:
                            return (a>0) + (b>0) + (c>0) + (d>0)

  • 0

    Hello, Stefan~ can you help me with my question I posted in the discussion. I am a little confused about the difference between Java and Python.
    here is the link:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.