You are not logged in. Please login at to post your questions!


Max Subarray GCD - Editorial


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 :

    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

himanshujaju's gravatar image

accept rate: 0%

edited 26 Nov '15, 12:33

admin's gravatar image

0★admin ♦♦


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 :)


answered 02 Dec '15, 11:42

admin123's gravatar image

accept rate: 28%

edited 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 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

rajat1603's gravatar image

accept rate: 4%


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?



answered 26 Nov '15, 10:56

rishabhshah's gravatar image

accept rate: 0%


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

(26 Nov '15, 19:26) rajat16037★

Thanks a lot for the code and the explanation. I understood it now.

(01 Dec '15, 11:55) rishabhshah2★

I used sliding window with segment tree.


answered 27 Nov '15, 01:17

rahul_nexus's gravatar image

accept rate: 13%

Thanks for the editorial


answered 16 Jan '16, 03:07

google_shiva's gravatar image

accept rate: 0%

It will be great if a code is provided for this method.....


answered 26 Nov '15, 18:58

pranavg189's gravatar image

accept rate: 25%

(26 Nov '15, 19:24) rajat16037★ 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

mukul_chandel's gravatar image

accept rate: 42%

Isnt the block idea a bit like that in Mo's Algorithm ?


answered 26 Nov '15, 21:42

theweblover007's gravatar image

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) himanshujaju6★

My O(N*N) soln passed
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

sanket407's gravatar image

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) himanshujaju6★

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

ankurverma1994's gravatar image

accept rate: 8%

Please include the link to practice and contest.


answered 01 Dec '15, 21:17

theweblover007's gravatar image

accept rate: 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

jones13's gravatar image

accept rate: 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

jones13's gravatar image

accept rate: 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

jones13's gravatar image

accept rate: 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


answered 16 Jan '16, 02:06

maverick_10's gravatar image

accept rate: 0%

Thanks for the editorial


answered 16 Jan '16, 03:06

google_shiva's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 25 Nov '15, 13:17

question was seen: 5,844 times

last updated: 16 Jan '16, 03:07