Getting TLE in sum of perfect squares problem

#1

In sum of perfect squares problem,i used the approach suggested in the video but still getting TLE in the last test case


Here is the link to my soln
Please help

#2

There is an issue with the last testcase , constraints are really tight for that one. One optimisation that you can do is

for(int i=1;i<=N;i++)
    {
        dp[i]=INT_MAX;
        for(auto j=1;j*j<=i;j++)
        {
                if(dp[i]>(1+dp[i-(j*j)]))
                    dp[i]=1+dp[i-(j*j)];
        }
    }

But its still won’t pass the last case

#3

So,u mean the issue is with the test case and ples can u explain how you optimized the code?

#4

Yes test case has an issue.
No it’s not optimized , I just saw you had used the break statement.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.