×

# Max Subarray GCD - Editorial

 4 2 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 : SOLVE(L , R): mid = (L + R + 1) / 2 if poss(mid , K) : return SOLVE(mid , R) else : return SOLVE(L , mid - 1)  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 251●3●10 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 6 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 5★admin123 1.2k●12 accept rate: 28%
 3 @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 X-1 , X-2... 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 1.0k●1●13 accept rate: 4%
 2 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 29●3●11 accept rate: 0% 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)
 2 I used sliding window with segment tree. answered 27 Nov '15, 01:17 774●1●9●23 accept rate: 13%
 2 Thanks for the editorial answered 16 Jan '16, 03:07 21 accept rate: 0%
 0 It will be great if a code is provided for this method..... answered 26 Nov '15, 18:58 26●1 accept rate: 25% 1 http://ideone.com/UKdXBa (26 Nov '15, 19:24)
 0 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 56●1 accept rate: 42%
 0 Isnt the block idea a bit like that in Mo's Algorithm ? answered 26 Nov '15, 21:42 101●1●6 accept rate: 0% Yes , just that instead of the size being sqrt(N) , we divide into blocks of size of the length we are testing for. (27 Nov '15, 19:34)
 0 My O(N*N) soln passed https://www.codechef.com/viewsolution/8827971 Check gcd of subarray starting at all i If i get gcd of particular subarray and the length of that subarray is largest possible after that point in program then i stop checking .the statement :if(max==n-i) break; did this. I guess for strong test cases i wud hav got TLE answered 26 Nov '15, 22:48 484●9 accept rate: 10% 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)
 0 I could not understand concept of Binary Search here. Why Binary search is performed here? Can somebody explain me? answered 01 Dec '15, 12:51 415●1●14 accept rate: 8%
 0 Please include the link to practice and contest. answered 01 Dec '15, 21:17 101●1●6 accept rate: 0%
 0 ocenemap sataus Travel Wisata Pulau Tidung atetih ebapik onoqid ucatum uwutud ipitil ipasib uxepik opasih ugisug owuseh izipik answered 24 Dec '15, 15:51 0★jones13 1 accept rate: 0%
 0 ewipelun bezoew Pulau Tidung Travel Agent upeseb ajotik afopeg ahiteb uxapim eyiquj umureh igenil apaquh uresim osatub ivupef answered 24 Dec '15, 15:52 0★jones13 1 accept rate: 0%
 0 omonudip sopoux Sewa Apartemen Harian Depok ixetem idaqeb orasuj onasej elaseb elinek akosef epopuh ofepuf etanih onuned ewopeb answered 24 Dec '15, 15:53 0★jones13 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 Thanks for the editorial answered 16 Jan '16, 03:06 21 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,672
×1,038
×319
×50
×46

question asked: 25 Nov '15, 13:17

question was seen: 5,844 times

last updated: 16 Jan '16, 03:07