Shortest subarray with GCD above 1 after at most k changes

Given an array of positive integers nums and an integer k, pick a contiguous subarray and change at most k of its elements to any positive integers you like. Return the minimum length of a subarray whose greatest common divisor can be made greater than 1 this way, or -1 if there is none.

Interface

Unless you agree on a different interface with the interviewer, assume:

• min_length(nums: list[int], k: int) -> int.

Example

nums = [1, 1, 1],        k = 0  ->  -1   # nothing can be changed and every gcd is 1
nums = [1, 7, 1],        k = 0  ->  1    # [7] alone has gcd 7
nums = [4, 9, 6, 1, 15], k = 1  ->  1    # with one change any single element works

Constraints

• 0 <= len(nums) <= 10^5, 1 <= nums[i], 0 <= k <= len(nums).

Clarifying questions

• With k >= 1, changing one element makes any single element work, so the answer is 1. Is that intended, or do you want the longest such subarray?
• Must the changed values be positive integers, and can they be any size?
• What should an empty array return?

What a strong answer covers

• The key fact: a set has gcd above 1 exactly when one prime divides all of it. A changed element can always be made a multiple of that prime, so for a prime p a window works when at most k of its elements are not multiples of p.
• Seeing that the minimum is almost always 1: it is 1 when k >= 1 or some element is above 1, and -1 only when k = 0 and every element is 1.
• For the longest-window version: only primes that divide some element matter (factor each value, or use a smallest-prime-factor sieve), and a two-pointer window per prime counting non-multiples gives O(n * P) for P candidate primes.
• Edge cases: all ones, k = 0, k >= n, very large values.

Follow-ups

• Return the length of the longest subarray that can be given a gcd above 1 with at most k changes. For [4, 9, 6, 1, 15] it is 2 with k = 0 ([9, 6]) and 4 with k = 1 ([9, 6, 1, 15], changing the 1).
• Return the subarray and the prime as well.
• Count the subarrays that need no changes at all.