Max Subarray GCD - Editorial

binary-search
easy-medium
editorial
gcd
ipc151a
ipcquestion

#1

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 denotes the value of gcd from [i … j] , where j is the end index of the block in which i lies. Similarly , Prefix 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 , 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).*


#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.


#3

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


#4

https://www.codechef.com/viewsolution/8830230
My O( N * sqrt(max(a*)) ) solution for this. It still passed and I have no idea why.


#5

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


#6

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


#7

I used sliding window with segment tree.


#8

I could not understand concept of Binary Search here. Why Binary search is performed here?

Can somebody explain me?


#9

@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.


#10

Please include the link to practice and contest.


#11

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 :slight_smile: https://www.codechef.com/viewsolution/8829901


#12

ocenemap sataus
Travel Wisata Pulau Tidung

atetih ebapik onoqid ucatum uwutud ipitil ipasib uxepik opasih ugisug owuseh izipik


#13

ewipelun bezoew
Pulau Tidung Travel Agent

upeseb ajotik afopeg ahiteb uxapim eyiquj umureh igenil apaquh uresim osatub ivupef


#14

omonudip sopoux
Sewa Apartemen Harian Depok

ixetem idaqeb orasuj onasej elaseb elinek akosef epopuh ofepuf etanih onuned ewopeb


#15

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


#16

Thanks for the editorial


#17

Thanks for the editorial


#18

#19

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


#20

Yes , just that instead of the size being sqrt(N) , we divide into blocks of size of the length we are testing for.