### SpartanWarrior's blog

By SpartanWarrior, history, 3 years ago,

 » 3 years ago, # |   +6 HintUse a range query data structure such as segment tree/sparse table. SolutionThe solution that I found most common after having solved the problem was using a range query data structure to answer queries on range [L, R] efficiently. I used a RQ DS too and so I'll explain a solution that uses segment tree.For a fixed point L, find the left most right boundary R such that $gcd([L, ..., R])$ is 1. Once we have such a value R, we can now move the left boundary. For any index i in [L, R], the $gcd([i, ..., R])$ will either be 1 or something greater. When we encounter a left boundary that makes gcd to something not 1, we start searching for another right boundary keeping the left boundary fixed. Among all such [L, R] endpoints, the one with maximum length is your answer.The solution using RQ DS is, imo, the most intuitive. The complexity you achieve this way is $O(n.log(n))$. You can use either segment tree or sparse table or any other logarithmic query associative DS to achieve this complexity. Note that the complexity actually seems like it's $O(n.log^2(n))$ because of gcd being in there but finding the gcd of an entire array is magically $O(n)$ approximately and not $O(n.({some \space log \space factor}))$.There also is a solution that uses something called a gcdqueue which is similar in structure to this but I do not understand it and will not explain.
•  » » 11 months ago, # ^ |   0 I actually am not able to understand with this is O(n). At first glance it seemed O(n^2) to me.What I thought was, for every j, the remove function in the tutorial in worst case removes no elements, which is analoguous here to moving the i pointer from j to the start (j times). So the no of iterations in the worst case: 1+2+3...n = O(n^2)Please let me know if I have made any mistake at any point... Would really appreciate the help...