279-2

class Solution {
public:
    bool check(int n){
        int sq = sqrt(n);
        return (sq*sq) == n;
    }

    int numSquares(int n) {
        // If perfect square, return 1.
        if(check(n))
            return 1;

        // If n = 4^k(8m+7), return 4.
        while(n%4 == 0)
            n /= 4;
        if(n%8==7)
            return 4;

        // If n is sum of 2 square, return 2.
        for(int i=1;i*i<=n;i++)
            if(check(n-(i*i)))
                return 2;

        // Else return 3.
        return 3;
    }
};