human
I found an interesting problem on https://leetcode.com/problems/perfect-squares/:
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.

I tried it in Python, but could not do it. Can you solve it?

What is a Python program to find the least number of perfect square numbers (for example, 1, 4, 9, 16,?
assistant
#Here is Python program to find the least number of perfect square numbers (for example, 1, 4, 9, 16, .

class Solution:
     def numSquares(self, n):
         """
         :type n: int
         :rtype: int
         """
         def is_square(n):
             return int(n**0.5) * int(n**0.5) == n
         
         if is_square(n): return 1
         for i in range(1, int((n**0.5) + 1)):
             if is_square(n - i*i):
                 return 2
         while (n & 3) == 0: n >>= 2
         if n & 7 == 7: return 4
         return 3