### vMortex's blog

By vMortex, history, 2 months ago,

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?

• -3

 » 2 months ago, # |   0 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
•  » » 2 months ago, # ^ |   +1 Bro, IDK whenever i open your profile i get motivated :)
•  » » » 2 months ago, # ^ |   0 lmao thanks man
•  » » » » 2 months ago, # ^ |   0 :)
•  » » 7 weeks ago, # ^ |   0 The segment tree solution is $O(N*log^{2}N)$
•  » » 7 weeks ago, # ^ |   0 If we use a two-pointer then it's solvable using a segment tree.124806066
 » 2 months ago, # |   0 I think this solution does not make use of segment tree, sparse table https://codeforces.com/contest/1549/submission/124572982
•  » » 2 months ago, # ^ |   0 Interesting, I didn't know it was possible.
•  » » 2 months ago, # ^ |   0 thanks.
•  » » » 2 months ago, # ^ |   0 welcome :)
 » 2 months ago, # | ← Rev. 2 →   +3 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.
•  » » 2 months ago, # ^ |   0 should i calculate a running gcd? could you explain a bit more. I think this uses exactly what you said https://codeforces.com/contest/1549/submission/124572982 but i'm not sure about the time complexity.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   +3 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.
 » 7 weeks ago, # |   0 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.
•  » » 7 weeks ago, # ^ |   0 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.