Prerequisites : Binary Search , GCD Properties Difficulty : Easy  Medium Expected Complexity : O(N * logn * p) , p = max number of steps to calculate GCD. Editorial : The most basic property of GCD is : gcd(i , j , k) = gcd(i , gcd(j , k)). Also , gcd(i,gcd(j,k)) <= gcd(j,k). Most part of our solution is based on this. The first thing we can see is that if a subarray of size Q has gcd value >= K , then we can for sure find a subarray of size < Q whose gcd value is >= K. Once we know this , we can binary search on the length of the subarray in the following way :
Now, we just need to create our poss() function , which takes in the length of subarray we are checking for and the minimum gcd value we are looking for as parameters. For every index i in [0,N  length] , we need to check if the subarray [i , i + length  1] has a gcd value >= K. If there is any index which satisfies , we will return true. Else we return false. To check , we could use a segment tree which stores gcd value for every segment. The overall complexity would be O(N * logn * logn * p) , which would eventually TLE as segment tree comes with a high constant factor. We can also calculate this in O(N * p) using a very simple trick. Divide the entire array into blocks of "length of subarray". Maintain two arrays suffix and prefix. Suffix[i] denotes the value of gcd from [i .. j] , where j is the end index of the block in which i lies. Similarly , Prefix[i] denotes the value of gcd from [a .. i] , where a denotes the starting index of the block in which i lies. This can be calculated easily in linear time. Now how does this exactly help us ? For any index i , we can calculate the GCD of the subarray [i .. i + length  1] by calculating the gcd of [i .. j] and [j + 1 .. i + length  1] , where j is the ending of the block in which i lies. Thus for every index i , gcd value is gcd(suffix[i] , prefix[i + length  1]). Our poss() function works in O(N * p) and we are calling it at most logN times , hence the total time complexity is O(N * logN * p).
This question is marked "community wiki".
asked 25 Nov '15, 13:17

Well if segment tree gives TLE due to large constant factor so it can be solved using $sparse$ $table$ which is more efficient method than any one described here it is O(n log n) we use sparse table for range minimum so instead of storing minimum value we store gcd and at time of query we need to find gcd of two value according to L and R so if this question was to find gcd of range(L,R) then everything will be same only min function replaced by gcd function but in this problem at query time we need to find the range of sub array according to K we need to traverse back so it need some modification you can take a look at my solution :) https://www.codechef.com/viewsolution/8829901 answered 02 Dec '15, 11:42

@ankurverma1994 , we are doing a binary search here on the answer , if we have a subarray of size 'X' with gcd >= k , then we will also have subarrays of size X1 , X2... 2, 1 with gcd >= k and if we dont have any subarray of size X with gcd >= k , we we wont have subarrays of size > X with gcd >= k , so we can binary search on answer. answered 01 Dec '15, 19:31

Hi Thanks for the editorial. I am unable to understand the trick that you have mentioned which doesn't involve segment trees. Can you help me with that? Thanks. answered 26 Nov '15, 10:56
2
We can perform a binary Search on answer while l < r: mid = (l + r) / 2 if check(mid): l = mid + 1 else: r = mid Now we just need to write an efficient check function Now suppose we want to check if any subarray of size 'X' exists which has GCD >= K , To do this , we divide the array in blocks of size 'X' and calculate the prefix and suffix GCD for each block , this will help us calculating the GCD of any block of size 'X' in O(1) time with O(N) pre processing. The complexity of this solution is O(N * LOGN * P) where P is time taken for calculating GCD http://ideone.com/UKdXBa
(26 Nov '15, 19:26)
Thanks a lot for the code and the explanation. I understood it now.
(01 Dec '15, 11:55)

I used sliding window with segment tree. answered 27 Nov '15, 01:17

https://www.codechef.com/viewsolution/8830230 My O( N * sqrt(max(a[i])) ) solution for this. It still passed and I have no idea why. answered 26 Nov '15, 20:55

My O(N*N) soln passed
https://www.codechef.com/viewsolution/8827971 answered 26 Nov '15, 22:48
I had tried a segment tree solution , and my brute didnt check for your "if" condition. Thanks for notifying though!
(27 Nov '15, 19:34)

I could not understand concept of Binary Search here. Why Binary search is performed here?
answered 01 Dec '15, 12:51

Please include the link to practice and contest. answered 01 Dec '15, 21:17

ocenemap sataus Travel Wisata Pulau Tidung atetih ebapik onoqid ucatum uwutud ipitil ipasib uxepik opasih ugisug owuseh izipik answered 24 Dec '15, 15:51

ewipelun bezoew Pulau Tidung Travel Agent upeseb ajotik afopeg ahiteb uxapim eyiquj umureh igenil apaquh uresim osatub ivupef answered 24 Dec '15, 15:52

omonudip sopoux Sewa Apartemen Harian Depok ixetem idaqeb orasuj onasej elaseb elinek akosef epopuh ofepuf etanih onuned ewopeb answered 24 Dec '15, 15:53

Hi can anyone please help me in figuring out why I am getting TLE on this problem My code passed using two pointer and segment tree but it gave tle with binary search and segment tree https://www.codechef.com/viewsolution/9180833 answered 16 Jan '16, 02:06
