Given an Array of size ‘N’ and a parameter ‘K’.
Find the length of the longest contiguous sub-array whose GCD is >= k
Constaints
2 <= N <= 5 * 10 ^ 5
1 <= arr[i] , K <= 10 ^ 6
Sample
Input
5 9
10 20 5 15 45
Output
2
Input
6 10
15 30 10 20 30 40
Output
5
will the answer always be possible ?
length = 0 in that case 
Basic idea : only log(n) distinct gcd are possible starting at any point.
we can find max length for every possible gcd starting at index i in log(n) time.
complexity of solution becomes n * log(n)^2
can it be done in n * log(n) ?
Here is my Nlogn Solution
Solution 1
We construct a sparse Table and of GCDs O(nlogn)
Now for every starting point ‘i’, we find the rightmost point ‘j’ which gives gcd(arr[i] , arr[i + 1] … arr[j]) >= k) , this can be done with binary search on sparse table O(logn) . so for every i , we take max of j - i + 1 for answer
Total O(nlogn) time and space
Solution 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
answer is l - 1
now for check(X)
We need to see if any subarray of size ‘X’ exists which gives gcd >= k
Now we can do this check in O(N) by dividing the array into blocks of size ‘X’ and for each block , calculate its prefix and suffix gcd and then we can get gcd of any subarray of size ‘X’ in O(1) time
total time -> O(nlogn)
total space -> O(n)
You don’t even need the idea that only log(n) distinct gcd’s will be there.
You can make use of the fact that gcd[i \dots j + 1] will be \leq gcd[i \dots j] and thus doing a binary search
Each of us is ignoring the fact that gcd computation also takes log(max(a,b)) time
both the solutions are nice though =D
gcd(a , b) takes log(max(a,b)) time but calculating gcd of N numbers takes about O(N + log(max)) time so the overall complexity of the algo is not supposed to be very high.
I just coded it and it is working in less than 0.5 seconds on random cases so i think N = 5 * 10 ^ 5 and K , arr[i] <= 10 ^ 6 constraints with a 2 second time limit is fine .
Any suggestions?
I had set a very similar question before for intra-college event, though that contest was not public.
link to question
seems fine to me 