Lagrange's four-square theorem - Java


  • 0
    K

    beats 97.55% .

    public class Solution {
        public int numSquares(int n) {
            while (n % 4 == 0) n /= 4;
            if (n % 8 == 7) return 4;
            for (int a = 0; a * a <= n; ++a) {
                int b = (int) Math.sqrt(n - a * a);
                if (a * a + b * b == n) {
                    return (a != 0 && b != 0) ? 2 : 1;
                }
            }
            return 3;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.