Perfect Squares

 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.

class Solution {
     bool isSquare(int n){
        int sq=sqrt(n);
        return n==sq*sq;
    }
public:
    int numSquares(int n) 
    {
     if(isSquare(n)) return 1;
        int count=n;
        while(count%4==0){
            count/=4;
        }
        
        if(count%8==7) return 4;
        
       
        count=1;
        while(count*count<n){
            if(isSquare(n-count*count)) return 2;
            count++;
        }
        
        return 3;
        
    }
    
//     int numSquares(int n) {
//         if(n<4)return n;
//         vector<int> v;
//         int i=1;
//          while(i*i<=n)
//          {
//              v.push_back(i*i);
//              ++i;
//          }
//           if(v.back()==n)return 1;
//        long int dp[v.size()][n+1];
//         memset(dp,0,sizeof(dp));
//         for(int i=0;i<v.size();++i)
//         {
//             for(int j=1;j<=n;++j)
//             {
//                 if(i==0)
//                 {
//                     dp[i][j]=j;
//                 }
//                 else if(j<v[i])
//                 {
//                     dp[i][j]=dp[i-1][j];
//                 }
//                 else
//                 {
//                     dp[i][j]=min(dp[i-1][j],dp[i][j%v[i]]+j/v[i]);
//                 }
//             }
//         }
        
//         return dp[v.size()-1][n];
    // }
};