Fewest Adjacent-GCD Operations to Turn Every Array Element into 1

You are given an array nums of positive integers. In one operation, you choose an index i with 0 <= i < len(nums) - 1 and replace either nums[i] or nums[i + 1], but not both, with the greatest common divisor (GCD) of those two values.

Return the minimum number of operations needed to make every element of nums equal to 1. If that is impossible, return -1.

Function Signature

def min_operations_to_all_ones(nums: list[int]) -> int:

Rules

• gcd(a, b) is the largest positive integer that divides both a and b; for example, gcd(12, 18) = 6 and gcd(4, 9) = 1.
• Operations are applied one at a time, and each one sees the values left by the previous operations.
• Return 0 if every element is already 1.

Constraints

• 2 <= len(nums) <= 50
• 1 <= nums[i] <= 10^6

Examples

Example 1

Input:  nums = [6, 10, 15]
Output: 4

One optimal sequence: replace 10 with gcd(10, 15) = 5, giving [6, 5, 15]; replace 6 with gcd(6, 5) = 1, giving [1, 5, 15]; replace 5 with gcd(1, 5) = 1, giving [1, 1, 15]; replace 15 with gcd(1, 15) = 1, giving [1, 1, 1]. No sequence of three operations works.

Example 2

Input:  nums = [3, 1, 9, 1]
Output: 2

Replace 3 with gcd(3, 1) = 1, then replace 9 with gcd(9, 1) = 1.

Example 3

Input:  nums = [4, 6, 8]
Output: -1

Every value is even, so every GCD that can be formed is even and no element can ever become 1.

Make Every Element 1 with Adjacent GCD Replacements

You are given an array nums of positive integers. In one operation you choose an index i with 0 <= i < len(nums) - 1 and replace either nums[i] or nums[i + 1], but not both, with the greatest common divisor (GCD) of those two values.

Return the minimum number of operations needed to make every element of nums equal to 1. If that is impossible, return -1. Return 0 if every element is already 1.

Rules:

• gcd(a, b) is the largest positive integer that divides both a and b; for example, gcd(12, 18) = 6 and gcd(4, 9) = 1.
• Operations are applied one at a time, and each one sees the values left by the previous operations.

Implement min_operations_to_all_ones(nums), which returns an integer.

Constraints:

• 2 <= len(nums) <= 50
• 1 <= nums[i] <= 10^6
• No input value, GCD or answer exceeds 2^31 - 1, so 32-bit integers suffice in every language.

Example 1:

Input: nums = [6, 10, 15]
Output: 4

Explanation: Replace 10 with gcd(10, 15) = 5, giving [6, 5, 15]; replace 6 with gcd(6, 5) = 1, giving [1, 5, 15]; replace 5 with gcd(1, 5) = 1, giving [1, 1, 15]; replace 15 with gcd(1, 15) = 1, giving [1, 1, 1]. No sequence of three operations works.

Example 2:

Input: nums = [3, 1, 9, 1]
Output: 2

Explanation: Replace 3 with gcd(3, 1) = 1, then replace 9 with gcd(9, 1) = 1.

Hints

1. Once some element equals 1, how many operations does each remaining non-1 element need, and can any of them be skipped?
2. Before any 1 exists, every value in the array is the GCD of some contiguous stretch of the original array. Which stretches could ever produce a 1?
3. If the GCD of the whole array is greater than 1, can a 1 ever appear?

Approach

Let n = len(nums) and c = the number of elements already equal to 1. Each operation changes exactly one element, and every element that is not 1 must change at least once, so at least n - c operations are needed. If c > 0, that many suffice: repeatedly pair a 1 with a non-1 neighbor and overwrite the neighbor with gcd(1, x) = 1, spreading the 1s outward. So the answer is n - c (which is 0 when every element is already 1).

If c = 0, a 1 must first be created. Invariant: at any moment, each element equals the GCD of some contiguous segment of the original array that contains its position, and one operation can grow that segment by at most one neighboring element. So the first 1 needs a contiguous window of the original array whose GCD is 1, and building it from a window of length L takes at least L - 1 operations; folding GCDs left to right across the shortest such window achieves exactly L - 1. After that, the other n - 1 elements each need one more operation, and none of them can have been fixed earlier, because no 1 existed before. The answer is (L - 1) + (n - 1). If no window has GCD 1 (equivalently, the GCD of the whole array exceeds 1), every reachable value keeps a common factor greater than 1 and the answer is -1.

Implementation: for each start i, keep a running GCD while extending j to the right, stop at the first j where it reaches 1, and track the minimum j - i. Edge cases: an all-ones array returns 0; a single non-coprime pair returns -1; an existing 1 makes the window search unnecessary. All values stay at or below 10^6, so 32-bit integers suffice.

• Time complexity: O(n^2 log M), where M is the largest value in nums
• Space complexity: O(1)