Summary of 4 different solutions (BFS, DP, static DP and mathematics)


  • 257
    Z

    Came up with the 2 solutions of breadth-first search and dynamic programming. Also "copied" StefanPochmann's static dynamic programming solution (https://leetcode.com/discuss/56993/static-dp-c-12-ms-python-172-ms-ruby-384-ms) and davidtan1890's mathematical solution (https://leetcode.com/discuss/57066/4ms-c-code-solve-it-mathematically) here with minor style changes and some comments. Thank Stefan and David for posting their nice solutions!

    1.Dynamic Programming: 440ms

    class Solution 
    {
    public:
        int numSquares(int n) 
        {
            if (n <= 0)
            {
                return 0;
            }
            
            // cntPerfectSquares[i] = the least number of perfect square numbers 
            // which sum to i. Note that cntPerfectSquares[0] is 0.
            vector<int> cntPerfectSquares(n + 1, INT_MAX);
            cntPerfectSquares[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                // For each i, it must be the sum of some number (i - j*j) and 
                // a perfect square number (j*j).
                for (int j = 1; j*j <= i; j++)
                {
                    cntPerfectSquares[i] = 
                        min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1);
                }
            }
            
            return cntPerfectSquares.back();
        }
    };
    

    2.Static Dynamic Programming: 12ms

    class Solution 
    {
    public:
        int numSquares(int n) 
        {
            if (n <= 0)
            {
                return 0;
            }
            
            // cntPerfectSquares[i] = the least number of perfect square numbers 
            // which sum to i. Since cntPerfectSquares is a static vector, if 
            // cntPerfectSquares.size() > n, we have already calculated the result 
            // during previous function calls and we can just return the result now.
            static vector<int> cntPerfectSquares({0});
            
            // While cntPerfectSquares.size() <= n, we need to incrementally 
            // calculate the next result until we get the result for n.
            while (cntPerfectSquares.size() <= n)
            {
                int m = cntPerfectSquares.size();
                int cntSquares = INT_MAX;
                for (int i = 1; i*i <= m; i++)
                {
                    cntSquares = min(cntSquares, cntPerfectSquares[m - i*i] + 1);
                }
                
                cntPerfectSquares.push_back(cntSquares);
            }
            
            return cntPerfectSquares[n];
        }
    };
    

    3.Mathematical Solution: 4ms

    class Solution 
    {  
    private:  
        int is_square(int n)
        {  
            int sqrt_n = (int)(sqrt(n));  
            return (sqrt_n*sqrt_n == n);  
        }
        
    public:
        // Based on Lagrange's Four Square theorem, there 
        // are only 4 possible results: 1, 2, 3, 4.
        int numSquares(int n) 
        {  
            // If n is a perfect square, return 1.
            if(is_square(n)) 
            {
                return 1;  
            }
            
            // The result is 4 if and only if n can be written in the 
            // form of 4^k*(8*m + 7). Please refer to 
            // Legendre's three-square theorem.
            while ((n & 3) == 0) // n%4 == 0  
            {
                n >>= 2;  
            }
            if ((n & 7) == 7) // n%8 == 7
            {
                return 4;
            }
            
            // Check whether 2 is the result.
            int sqrt_n = (int)(sqrt(n)); 
            for(int i = 1; i <= sqrt_n; i++)
            {  
                if (is_square(n - i*i)) 
                {
                    return 2;  
                }
            }  
            
            return 3;  
        }  
    }; 
    

    4.Breadth-First Search: 80ms

    class Solution 
    {
    public:
        int numSquares(int n) 
        {
            if (n <= 0)
            {
                return 0;
            }
            
            // perfectSquares contain all perfect square numbers which 
            // are smaller than or equal to n.
            vector<int> perfectSquares;
            // cntPerfectSquares[i - 1] = the least number of perfect 
            // square numbers which sum to i.
            vector<int> cntPerfectSquares(n);
            
            // Get all the perfect square numbers which are smaller than 
            // or equal to n.
            for (int i = 1; i*i <= n; i++)
            {
                perfectSquares.push_back(i*i);
                cntPerfectSquares[i*i - 1] = 1;
            }
            
            // If n is a perfect square number, return 1 immediately.
            if (perfectSquares.back() == n)
            {
                return 1;
            }
            
            // Consider a graph which consists of number 0, 1,...,n as
            // its nodes. Node j is connected to node i via an edge if  
            // and only if either j = i + (a perfect square number) or 
            // i = j + (a perfect square number). Starting from node 0, 
            // do the breadth-first search. If we reach node n at step 
            // m, then the least number of perfect square numbers which 
            // sum to n is m. Here since we have already obtained the 
            // perfect square numbers, we have actually finished the 
            // search at step 1.
            queue<int> searchQ;
            for (auto& i : perfectSquares)
            {
                searchQ.push(i);
            }
            
            int currCntPerfectSquares = 1;
            while (!searchQ.empty())
            {
                currCntPerfectSquares++;
                
                int searchQSize = searchQ.size();
                for (int i = 0; i < searchQSize; i++)
                {
                    int tmp = searchQ.front();
                    // Check the neighbors of node tmp which are the sum 
                    // of tmp and a perfect square number.
                    for (auto& j : perfectSquares)
                    {
                        if (tmp + j == n)
                        {
                            // We have reached node n.
                            return currCntPerfectSquares;
                        }
                        else if ((tmp + j < n) && (cntPerfectSquares[tmp + j - 1] == 0))
                        {
                            // If cntPerfectSquares[tmp + j - 1] > 0, this is not 
                            // the first time that we visit this node and we should 
                            // skip the node (tmp + j).
                            cntPerfectSquares[tmp + j - 1] = currCntPerfectSquares;
                            searchQ.push(tmp + j);
                        }
                        else if (tmp + j > n)
                        {
                            // We don't need to consider the nodes which are greater ]
                            // than n.
                            break;
                        }
                    }
                    
                    searchQ.pop();
                }
            }
            
            return 0;
        }
    };

  • 52
    A

    why Static Dynamic Programming is faster than Dynamic Programming


  • 2
    C

    The table can be reused.


  • 4
    Z

    Yes, for example, if you first call numSquares(100), a table with size 101 will be built. Then if you call numSquares(10), the function doesn't need to rebuild the table and it will immediately return the entry with index 10.


  • 0
    B

    thanks for the explanation.


  • 16
    T

    static DP is equivalent to DP if you only call function once. However, if you call it several times, static vector would be reused and make whole test cases much faster.


  • 2
    B

    Static vector is taking advantage of the online judge procedure. Kind of weird isn't it? By the way, so curious about the magic 4^k*(8*m + 7)!


  • 1
    X

    My solution is 200ms on leetcode.
    I think this can be regarded as dfs.
    start from n, minus square one by one, finally, reach zero. in all these solution, we keep the minimum.
    I use a variable level to avoid going to unnecessary deep level. thus save a lot of time.

    class Solution {
    public:
        int numSquares(int n) {
            vector<int> nums(n+1);
            return helper(n, nums, n);
        }
        
        int helper(int n, vector<int>& nums, int level) {
            if (!n)
                return 0;
            if (nums[n])
                return nums[n];
            if (!level)
                return -1;
                
            --level;
            const int up = sqrt(n);
            int ans = n;
            int res = n;
            for (int i=up; i>=1 && res; i--) {
                res = helper(n-i*i, nums, min(ans, level));
                if (res >= 0)
                    ans = min(ans, res);
            }
            nums[n] = ans + 1;
            return nums[n];
        }
    };

  • 0
    E

    Thanks for sharing.


  • 0
    G

    Can someone explain the magic 4^k(8m + 7)! please?


  • 0
    G
    This post is deleted!

  • 1
    Z

    The magic 4^k(8m+7) can be derived from Lagrange's Four Square theorem and Legendre's three-square theorem.

    1. Based on Lagrange's Four Square theorem, there are only 4 possible results: 1, 2, 3, 4.

    2. Based on Legendre's three-square theorem, if n can be written as 4^k(8m+7), it can't be represented as the sum of 1 or 2 or 3 integers.

    I have also updated the comment in the mathematical solution.


  • 0
    E

    My DP solution with memoization. It is not fast as the static DP solution though (my run time is 186ms); not sure why yet.

    public int numSquares(int n) {
        
        int[] res = new int[n+1];
        for(int i=1; i<=n; i++)
            res[i] = Integer.MAX_VALUE; // memoize the result in a vector, i.e., res[i] stores the length of target i
    
        return getResult(res, n)[n];
    }
    
    public int[] getResult(int[] res, int k) {
        if(k==1) {
            res[k] = 1;
            return res;
        }
        
        // if already stored, just return the value
        if(res[k]<Integer.MAX_VALUE)
            return res;
        // if not stored yet, compute it recursively.
        else {
            for(int i=1; i<=k; i++) {
                int is = i*i;
                if(is>k) break; // only need to run the for loop up to sqrt(i)
                res[k] = Math.min(res[k], 1+getResult(res, k-is)[k-is]);
            }
        }
        return res;
    }

  • 0
    Z

    I see at least two issues in your code.

    1. res is a local array and it is not static, so the result obtained during one numSqaures call is not saved for subsequent numSquares calls.
    2. Every time numSquares is called, a new res array is allocated and is never deleted. The memory is leaking.

  • 0
    S

    I don't understand the two issues you mentioned. 1. why does numSquares() need to be called multiple times to calculate the result for n it takes as argument? 2. Wouldn't Garbage Collection in Java take care of this? Thanks!


  • 2
    Z
    1. Please read the comments in the solution of Static Dynamic Programming to understand why a static array can speed up multiple numSquares() calls. In short, if numSquares(100) is firstly called, a static array with size 100 is calculated and stored even after the call is ended (because the array is static). Then if numSqaures(50) is called, the function simply returns the 50-th element of the static array without any calculation.

    2. The solutions posted here are all written in C++. There is no garbage collection in standard C++.


  • 0
    J

    what is the time complexity of the BFS solution? Thanks...


  • 1
    Z

    In general, the time complexity of BFS is O(|V| + |E|) where |V| is the number of vertices in the graph and |E| is the number of edges in the graph. As in the constructed graph, |V| = n and |E| <= n^2. The time complexity of the BFS here is O(n^2).


  • 0
    J

    Thanks so much for your detailed explanation - the general case and this special case :)


  • 0
    Z

    still confused..I think that static elements can share between objects of the same class. However, there's a single object of Solution. How could the static vector be faster? Thx.


Log in to reply
 

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