Two DP solutions enclosed with a mathematical one in C, well-commented


  • 1
    //AC - 144ms - DP method;
    int numSquares(int n)
    {
        int *mins = (int*)malloc(sizeof(int)*(n+1)); //store the minimal number of the PerfectSquare;
        mins[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            int min = INT_MAX;
            int square = 1;
            for(int r=1; square <= i; r++) //traverse the previous result to get the min;
            {
                int t = mins[i-square]+1;
                min = t < min? t : min;
                square = r*r;
            }
            mins[i] = min;
        }
        return mins[n];
    }
    

    Another DP solution but optimised further to avoid redundant operation by static feature in C.

    int helper(int n)
    {
        static int mins[1000000]; //using static feature to avoid redundant searching;
        mins[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            int min = INT_MAX;
            int square = 1;
            for(int r=1; square <= i; r++)
            {
                int t = mins[i-square]+1;
                min = t < min? t : min;
                square = r*r;
            }
            mins[i] = min;
        }
        return mins[n];
    }
    
    //AC - 124ms;
    int numSquares(int n)
    {
        return helper(n);
    }
    

    //AC - 4ms - mathematical method;
    int numSquares(int n)
    {
        //Based on Lagrange's Four Square theorem, there 
        //are only 4 possible results: 1, 2, 3, 4.
        //The result is 4 if and only if n can be written in the form of 4^k*(8*m + 7).
        while(n%4 == 0) //(n & 3) == 0
            n >>= 2;
        if(n%8 == 7)
            return 4;
        for(int a=0; a*a <= n; ++a) //consider 1 and 2;
        {
            int b = sqrt(n-a*a);
            if(a*a + b*b == n)
                return 1+!!a; //if a==0, then return 1 otherwise return 2;
        }
        return 3;
    }

Log in to reply
 

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