Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An adjacent GCD replacement cannot change the GCD of the whole array. If it exceeds one, success is impossible. Existing ones can spread to every non-one in one operation each. Otherwise, first create a one from the shortest contiguous interval whose GCD is one, then spread it.

Approach

Compute the overall GCD and count ones. Return -1 for overall GCD greater than one, or n - ones when any ones already exist. In the remaining case, extend a running GCD from every starting index until it becomes one, retaining the shortest interval length L. Creating a one from those L values takes L - 1 adjacent combinations; changing all other positions then takes n - 1. Return their sum.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        def gcd(a, b):
            if a % b == 0:
                return b
            return gcd(b % a, a)

        n = len(nums)
        ones = 0
        g = 0

        for x in nums:
            g = gcd(g, x)
            if x == 1:
                ones += 1

        if g > 1:
            return -1
        elif ones > 0:
            return n - ones

        # case 3- no 1s but gcd is 1
        mlen = n # minimum len of subarray with gcd = 1

        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    mlen = min(mlen, j - i + 1)
                    break

        return (mlen - 1) + (n - 1)

Complexity analysis

Let n = nums.length and V = max(nums). Worst-case time is O(n^2 log(V + 1)) for running gcds over candidate intervals, including the initial O(n) pass. The all-one case returns after that pass. Auxiliary space is O(log(V + 1)) for the recursive gcd stack; there is no interval table. Arithmetic operands remain bounded by V.