Getting TLE for hackerearth problem( Mike and GCD issues)

help
1

here is the link for the problem

And link for my approach is link

There i am calculating gcd for all the values in my code…Maybe it is the reason for TLE, Anyone suggest a better approach to pass all the cases…

please help i am a beginner…
Thanks in advance!!

2

you can find the prime factors of the numbers from left to right in the array and assign the prime factors the index value of the array element, if the prime factors has not appeared before otherwise assign the index value of the factor as the answer of that element and then assign the current index value to the prime factor. Similarly , do the same from right to left and take the minimum difference answer from both.

For any doubt , you can take help from my submission :

Good luck !

2 Likes
3

Bro can you please explain lines 2 and 3 in your explaination… it is not clear

4

suppose u have the array : a[ ] = { 4,6,8,9,12 }
Now, starting with the first element 4, we will find out all of its prime factors which in this case is 2 only.
Now, we will create a temp array for checking if any prime factor has came before or not.
so , in this case temp[2]=0, so we will assign temp[2]= 1, where 1 is the index of 4.

Now , moving to the next element , we have 6, whose prime factors are 2 and 3.

As , 2 has occured before so we will put ans[2]=max(ans[2],temp[2]) , where ans[2] is the current answer of the element having index 2.
Now , we will update the temp[2]=2, where 2 is the index of 6.
Similarly, temp[3]=2

Similarly , check for next element upto the rightmost element.
After doing that , use the same process from step 1 from right to left and u will get the answer.

1 Like
5

Thank you very much bro!!