As we know, if $$$x\neq 1$$$ and $$$x\neq y$$$, then either $$$gcd(x,y)=x$$$ or $$$gcd(x,y)<=\frac{x}{2}$$$. That means for each element $$$a_i$$$ in the array, it will change at most $$$log(a_i)$$$ times before it becomes $$$1$$$.
So we can implement the process, but for every round we only consider the element that will change, then we just do $$$O(N*log(a_i))$$$ times change.
How to find the elements that will change in the next round? We can see that elements will change in the next round, are only in the elements change in this round and their left element, so we just check them. The number of elements we check is $$$O(N*log(a_i))$$$ too.
solution
Nice solution :)
Can you/someone please help to elaborate this? I'm quite fascinated by this solution. I tried doing Brute Force for this problem submission:121999001 which got TLE. I did not find any way to optimize it which is mentioned in this post. It would be really nice if I could get any additional help in understanding the solution.
You check all elements in every round of BruteForce. There can be $$$N$$$ rounds , so it has a $$$O(N^2)$$$ complexity, may lead to TLE.
We can see that elements will change in the next round, are only in the elements change in this round and their left element, so we just check them.
Can you explain this sentence again?
For example, if $$$N=10$$$, and $$$a_3,a_7$$$ change in this round, then we can assert that only $$$a_2,a_3,a_6,a_7$$$ may change in the next round. We can only check whether $$$a_2,a_3,a_6,a_7$$$ will change in the next round. Other elements certainly won't change in the next round so we don't check them.
That's because: $$$a_i$$$ will change if $$$gcd(a_i, a_{i+1})\neq a_i$$$, so if both $$$a_i$$$ and $$$a_{i+1}$$$ does not change in this round, then $$$a_i$$$ won't change in the next round.
With the $$$\LaTeX$$$ markup, this looks like you're talking about factorials on first glance. You may want to consider instead writing this as: $$$x \neq y$$$. (Code is
x \neq y).Thanks! I've learned and fixed it.