Getting tle for test cases 2 and 3

#1

getting tle for test cases 2 and 3

#2

Hello bro, you are getting TLE because of this

	for(long long int  i=2;i<=(y/2);i++){
		if(isprime(i)==1){
			while(x%i==0){
				
				factorsum=factorsum+i;
				x=x/i;
			
			}
		}
	}

Because you are checking for 2 to y/2 nos. that it is prime or not so it is O(y)*(time to calculate that the no. is prime). So overall worst case complexity is around O(Y^(3/2)) or O(N^(3/2)).
You need to reduce your complexity. You can use rootN method of getting the primes.
Take the test case 1000000007 the answer will be 0.
Your code is not evaluating for the larger no. especially when the no. is prime also.
Try to use rootN approach of primes it will get accepted.
I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks :slight_smile:
Happy Coding !!

1 Like
#3

where can i find the video on root n approch

#4

@coe17b014 this is also incorrect, as factors(or i) >9 are firectly added, instead we need sum of digits for factors also, eg: if 11 is a factor, it contributes a sum of 2 and not 11.
Now coming for root N approach: every prime factor can be accounted when you iterate only till sqrt(N). here’s the pseudocode:
for i: 2 to sqrt(N)
if(N%i==0)
while(N%i==0)
factorsum = factorsum+get_digit_sum(i)
N=N/i

atlast if(N!=1)
then N is also a prime!, so factorsum = factorsum+get_digit_sum(N)

Now for video explanation you may refer the number theory section as it provides enough knowledge to understand above pseudocode.

1 Like
#5

% 9 at last does the work that is not wrong

#6

%9 doesn’t work!, eg for 97, sum should be 16 but 97%9 is 7.

#7

the sum of digits of 16 is also 7

#8

for example we take 22 factors are 2 and 11 sum is 13 .
sum of digits is 4

#9

We have to consider sum of digits only once! so you cannot take sum of digits of 16 again as you already took for 97.

#10

Please go through the question again.
for 22:
sum of digits of 22=4
now factors of 22 are 11(sum 2) and 2(sum 2), total sum of factors = 4!

1 Like