TLE in test case 2 boston number

#1

#include
using namespace std;
int fin(int ps){
int ans=0;
while(ps!=0){
int k=ps%10;
ans+=k;
ps/=10;
if(ans>=10){
ps+=ans;
ans=0;
}
}
return ans;
}
int prime(int n){
int x=n, ps=0, j;
for(int i=2; i<n; i++){
if(x%i==0){
j = i;
x/=i;
i–;
//cout << j;
ps+=j;
}
}
return ps;
}
int main() {
int n, num, spn, sn;
cin >> n;
num = prime(n);
//cout << num << endl;
spn = fin(num);
sn = fin(n);
//cout << spn << endl << sn;
if(sn==spn){
cout << true;
}
else{
cout << false;
}
return 0;
}

#2

@shraddhamishra812003_b58bd74465a696b0 hii shraddha see you mistakes in both prime and second function see this

#3

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.

#4

may you please describe my mistake I got your solution but i’m still in confusion

#5

Hello, @shraddhamishra812003_b58bd74465a696b0,

I am listing all the errors:

  1. You are iterating from 2 to N, and N could be as large as 1e9 (1000000000). So, the time complexity of your code is O(N) which would obviously give TLE taking constraints under consideration.

  2. In fin function of yours, this below code is extra, if you remove this it won’t affect your implementation.

     if(ans>=10){
       ps+=ans;
       ans=0;
  }

To avoid TLE, Iterate from 1 to sqrt(n) like this, in the end, if condition is necessary for cases if n is prime like (23, 41,…)

for(int i=2; i*i<=n; i++){
     if(x%i==0){
         j = i;
         x/=i;
         i--;
         ps+=j;
     }
}
if(n!=1){
     ps += n;
}
#6

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.