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)