One of the tags for Integers have friends problem is binary search but I am not able to figure out how to apply binary search without using segment tree and sparse table.(since i'm a beginner i actually don't know segment tree and sparse table). I want to do it using only binary search if it's possible. My approach: For a value X check if it's possible that max size of friend group is less than or equal to X, if i'm able to do this in O(n) then it's solved but i don't know how to do this in O(n). Am i missing something is there any other way to do it using binary search?
The idea is that you need to binary search a range GCD and find the largest possible range from the leftmost position to the rightmost. (essentially the largest friend group) In order to do this in O(NlogN) time, you need a sparse table (O(1) query and O(NlogN) construction) or segment tree (which may even be too slow). I don't think it's possible without a RMQ/Sparse Table
Bro, IDK whenever i open your profile i get motivated :)
lmao thanks man
If we use a two-pointer then it's solvable using a segment tree.
124806066
I think this solution does not make use of segment tree, sparse table https://codeforces.me/contest/1549/submission/124572982
Interesting, I didn't know it was possible.
there is a way to do it without binary search or DS entirely, which is just to maintain the points where the GCD changes as you loop right endpoints from $$$1$$$ to $$$n$$$. The GCD can only change $$$\approx \log{N}$$$ times so you can do this with a vector or something, then just pick the leftmost endpoint that isn't $$$1$$$.
I didn't remember the code entirely during contest so I just used sparse table template code for my solution.
should i calculate a running gcd? could you explain a bit more. I think this uses exactly what you said https://codeforces.me/contest/1549/submission/124572982 but i'm not sure about the time complexity.
It looks like you are keeping every GCD in the map (even ones that are no longer 'relevant').
Maybe it is hackable.
UPD: NVM, I did not see the assignment of the new map, I think your solution is fine, but is $$$log^2$$$ instead of $$$log$$$ because of the map.
The idea is to fix the left pointer and then binary search the right pointer with log n steps, using either a segment tree (log n) or a sparse table (nearly constant time), a fenwick tree (much harder to do and I don't recommend), a treap, or whatever. At the end of the day, the complexity will be nearly the same. Then the answer will be the length of this subarray.
Afaik fenwick trees can only be used for prefix-based operations. I think you won't be able to use a fenwick tree to find range-GCD.