Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - CPP - 279. Perfect Squares

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4800552.html

題目：


解答：

class Solution {
public:
    int numSquares(int n) {
        auto is_square = [](int n) -> bool {
            int s = sqrt(n);
            return n == s * s;
        };

        if (is_square(n)) {
            return 1;
        }

        while (n % 4 == 0) {
            n /= 4;
        }

        if (n % 8 == 7) {
            return 4;
        }

        for (int i = 1; i * i <= n; ++i) {
            if (is_square(n - i * i)) {
                return 2;
            }
        }

        return 3;
    }
};