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

• 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?

• 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?

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

• 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)``````

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