# Python BFS/Maths solution (402 ms, beating 92.71%)

• This solution uses some mathematics to speed the BFS solution a bit:

• Square of odd numbers ≡1 (mod 4) and square of even numbers ≡0 (mod 4) for all natural number k
• Lagrange's Four Square Theorem (The answer is at most 4)
• From the theorem: 4k and k gives the same answer (Proof: Suppose 4k equates some sum of squares, one of which is odd, then it takes at least 4 squares (4=1+1+1+1), which is the maximum. Now if every square is even (divisible by 4), then the expression is just that for k multiplied by 4, which is at least as good)

Now with these knowledge I never need to put multiples of 4 in the Tree.
Therefore I can look at only odd squares in the loop and doubles the speed.

On programming side, I'm just rather new to Python and I can't have optimal methods; just that my function does not call sqrt and does not implement a true queue (I never remove any element) to speed things up

The n%8==7 checking part comes from this fact:

• If k ≡ 7 (mod 8), the answer must be 4. (since k^2≡0,1,4 (mod 8) and 7=4+1+1+1)
It's a rather optional check, depending on the testing cases (for OJ's 100ms is saved)
``````class Solution(object):
def numSquares(self, n):
while not n%4:
n//=4
if n%8==7:
return 4
d={n:1}
l=[n]
i=0
while True:
k=1
while k*k<l[i]:
t=l[i]-k*k
while not t%4:
t//=4
if t not in d:
l.append(t)
d[t]=d[l[i]]+1
k+=2
if k*k==l[i]:
return d[l[i]]
i+=1
``````

On a side note, I don't think a programmer's required to know the four square theorem nor modular arithmetic so the acceptable time here is much longer (since tree is a lot bigger).

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