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


  • 0
    M

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


Log in to reply
 

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