Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
class Solution:
     def numSquares(self, n):
         import math
 
         def is_square(m):
             sqrt_m = int(math.sqrt(m))
             return sqrt_m * sqrt_m == m
         if is_square(n):
             return 1
         while (n & 3) == 0:
             n >>= 2
         if (n & 7) == 7:
             return 4
         sqrt_n = int(math.sqrt(n))
         for i in range(1, sqrt_n + 1):
             if is_square(n - (i * i)):
                 return 2
         return 3
class Solution:
     def numSquares(self, n):
         import math
 
         def is_square(m):
             sqrt_m = int(math.sqrt(m))
             return sqrt_m * sqrt_m == m
         if is_square(n):
             return 1
         while (n & 3) == 0:
             n >>= 2
         if (n & 7) == 7:
             return 4
         sqrt_n = int(math.sqrt(n))
         for i in range(1, sqrt_n + 1):
             if is_square(n - (i * i)):
                 return 2
         return 3