4ms C++ Solution Without DP or BFS


  • 6
    D
    class Solution {
        public:
        int numSquares(int n) {
            while (n % 4 == 0)    n /= 4;
            if (n % 8 == 7)    return 4;
            int m = sqrt(n);
            if (m * m == n)    return 1;
            if (n % 2 == 0)    n >>= 1;
            if (n % 4 == 3)    return 3;
            for (int i = 3; i * i < n; i += 4)
                if (n % i == 0) {
                    bool odd = true;
                    n /= i;
                    while (n % i == 0) {
                        odd = !odd;
                        n /= i;
                    }
                    if (odd)    return 3;
                }
            return 2;
        }
    };

  • 0
    Y

    How does this solution work?


  • 0
    W

    can you explain this solution?


  • 0
    D

    As we know, each positive integer n could be decomposed as sum of 4 squared numbers. Moreover, n could be decomposed as sum of 3 squared numbers if and only if n is not of form 4^t*(8k+7) for some non-negative integers k and t. Also, a sufficient and necessary condition for a positive integer n being decomposable to sum of two squared numbers is that each prime factor of n of form 4k+3 should have an even degree (i.e. if a prime p=4k+3 and p^(2t+1)|n for some non-negative integers k and t, then p^(2t+2)|n ).


  • 0
    W

    this seems to be a math solution instead of computer science solution. I guess interviewer wouldn't want to see such a solution during an interview, though it's really amazing.


Log in to reply
 

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