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