Longest Subarray gcd

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

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

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