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


  • 0
    A

    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
    P

    me too. And my code is like.

    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """  
            "TLE"
            # 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
                else:
                    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
    L

    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
    H

    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:
    https://leetcode.com/discuss/59005/why-the-dp-solution-runs-much-faster-in-java-than-in-python


Log in to reply
 

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