PreviousNext
Coding/Bits and math

Longest subarray GCD

Write codeHard35 min

Your task

Given a list of positive integers (length 1 to 2e5, each 1 <= x <= 1e9), return the length of the longest contiguous subarray whose GCD is strictly greater than 1. If no such subarray exists, return 0. A single element x > 1 counts as a length-1 subarray. The O(n^2) approach is too slow; aim for O(n log(maxval)).

Examples

longest_gcd_subarray(nums: list[int]) -> int
Example 1
Inputlongest_gcd_subarray([2, 4, 6, 3, 9, 12])
Output4