MSV - getting TLE

1

Why I am getting TLE in O(n.sqrt(maxA)) approach in Python.

problem link:

my solution:
(CodeChef: Practical coding for everyone)

2

I have not seen your code but If you are pretty sure that there is no other error and time complexity is tolerable then I suggest you to try some other programming language with same algorithm. Like C++, C or JAVA.

I once submitted solution on hacker rank in python which was giving TLE (taking around 13 seconds locally) and then I analysed my algorithm once again which I thought should be executed within time limit.

So I rewrote the same in C++ and it got excepted in time much lower than required time limit.

3

I think you should calculate sqrt out of the loop…
Because you are calculating sqrt for each iteration.
image

4

or instead of this u can write this
while(j*j <= i):
// do something
@pvimal816

5

@ssrivastava990 bro i used j*j<=i but still TLE
Link
but i used java same logic got AC

6

Yeah i know, these things happens with my friend too. … . .so i suggest please use c++ or java as much as possible , (python ka kuch nhi kah skte) ,tomorrow is icpc , so i suggest use java / c++
:slight_smile:
TRY your code in pypy3 :slight_smile:
CodeChef: Practical coding for everyone (MY FRIEND’s CODE)

7

Try once list instead of dictionary as you do in java.
may be its because heavy data structure.

8

https://www.codechef.com/viewsolution/27432650
here u go i copied your code and paste in lang pypy i accepted :slight_smile:

9

sometimes , instead of python we have to submit in pypy

10

Yes bro it is better but it depends on constraints that’s why i use dictionary
look at this just submitted same code in pypy got AC
Link

11

@ssrivastava990 I think you have mistakenly tagged me.

12

Read your solution but did’t got it.
Here is is my solution.
Initialize factors_cnt as 0, this will keep track of the number of elements divisible by the index at which the number is located. Factors_cnt is going to store the star value of cur element. How, I will answer that part later.
Iterate through input list and first check how many elements before cur element is divisible by cur element.
How would you that? For that we have factors_cnt, factors_cnt[cur_element] is the number of elements which are divisible by cur element.
Now once we have found cur element star value, the cur element is also divisible by it’s factors. Now find it’s factors and increase their count at factor_cnt[factor]++
Go through the solution and you will understand.