Problem Statement in English

You’re given a 0-indexed array nums of positive integers. In one operation, you can:

  • Choose two different indices i and i + 1 such that 0 <= i < nums.length, and replace either one of nums[i] or nums[i + 1] with gcd(nums[i], nums[i + 1]).

Your goal is to make all the elements of the array equal to 1 using the minimum number of operations. Return the minimum number of operations required to make all the elements of nums equal to 1. Return -1 if it is not possible to do so.

Approach

GCD is associative. That means taking the GCD of a contiguous subarray is the same as taking the GCD of the GCDs of its parts.

To make all elements equal to 1, we need at least one subarray with GCD equal to 1.

If there is already a 1 in the array, we can simply convert all other elements to 1 in N - number_of_ones operations.

So we need to find the smallest contiguous subarray with GCD equal to 1.

The answer is then length_of_subarray - 1 + (N - 1), where length_of_subarray - 1 is the number of operations to convert that subarray to 1s (since it taking the GCD of a pair of numbers counts as one operation), and N - 1 is the number of operations to convert the rest of the array to 1s.

Solution in Python


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)
        nOnes = 0

        for num in nums:
            if num == 1:
                nOnes += 1

        if nOnes > 0:
            return N - nOnes

        smallest = N + 1

        for i in range(N):
            currentGCD = nums[i]

            for j in range(i + 1, N):
                currentGCD = gcd(currentGCD, nums[j])

                if j - i + 1 > smallest:
                    break

                if currentGCD == 1:
                    smallest = min(smallest, j - i)
                    break

        return -1 if smallest == N + 1 else smallest + (N - 1)

Complexity

  • Time: $O(n^2 \times \log(\max(nums)))$
    Since for each subarray we are calculating the GCD which takes $O(\log(\max(nums)))$ time and there are $O(n^2)$ subarrays.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

Mistakes I Made

I messed up the final formula for calculating the result (I tried to figure out the rest after watching the initial part of NeetCode’s solution on YouTube).

And we are done.