How to improve this TLE code?


  • 0
    M
    class Solution {
    public:
        int numSquares(int n) {
            int dp[n+1];
            for( int i=0; i<=n;i++){
                dp[i]=i;
            }
        
            for( int i=1;i<=n/2;i++){
                int input=i*i;
                for(int j=1;j<n+1;j++){
                    if(j>=input){
                        int rom=j%input;
                        int divs=j/input;
                        dp[j]=min(divs+dp[rom],dp[j]);
                    }
                }
            }
            return dp[n];
        }
    };

  • 1
    R

    You can change the first loop to iterate up to sqrt(n):

    for( int i=1;i*i<=n;i++)
    

    This is safe to do because for larger i values input becomes greater than n and it causes divs to be 0.

    Another optimisation would be to start iterating from input in the second loop:

    for(int j=input;j<n+1;j++)

Log in to reply
 

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