Problem Description

You have an array nums of positive integers (0-indexed). You can perform the following operation any number of times:

• Choose any index i where 0 <= i < n - 1
• Replace either nums[i] or nums[i+1] with their greatest common divisor (GCD)

Your goal is to make all elements in the array equal to 1 using the minimum number of operations. If it's impossible to achieve this, return -1.

For example, if you have two adjacent elements like [6, 10], you could replace either the 6 or the 10 with their GCD which is 2, giving you either [2, 10] or [6, 2].

The key insight is that you need to determine:

1. Whether it's possible to reduce all elements to 1 (this is only possible if the GCD of all elements together equals 1)
2. If possible, what's the minimum number of operations needed

The solution considers two main cases:

• If there are already some 1s in the array, you can use each 1 to convert its neighbors to 1 through GCD operations (since GCD(1, any number) = 1)
• If there are no 1s initially, you first need to create at least one 1 by finding the shortest subarray whose GCD equals 1, then spread that 1 to all other elements

The operation count depends on how many elements need to be changed and the minimum steps required to create the first 1 (if needed).

Intuition

The first observation is that once we have a single 1 in the array, we can propagate it to all other elements. This is because GCD(1, x) = 1 for any positive integer x. So if we have a 1 at position i, we can make position i+1 equal to 1, then use that new 1 to convert position i+2, and so on. Similarly, we can propagate leftward.

If the array already contains some 1s, we don't need to create any. We just need to convert all non-1 elements to 1. Each non-1 element requires exactly one operation to become 1 (by taking GCD with an adjacent 1). So if we have cnt ones already, we need n - cnt operations.

The challenging case is when there are no 1s initially. We need to create at least one 1 first. To create a 1, we need to find two or more consecutive elements whose GCD equals 1. The key insight is that we want to find the shortest such subarray because:

• Creating a 1 from a subarray of length k requires k - 1 operations (we repeatedly take GCD of adjacent pairs until we reduce the entire subarray to a single 1)
• Once we have one 1, we need n - 1 more operations to propagate it to all other positions

Therefore, we search for the minimum length subarray whose GCD is 1. For each starting position i, we extend to position j and compute the GCD of elements from i to j. When this GCD becomes 1, we've found a candidate subarray of length j - i + 1.

If no such subarray exists (meaning the GCD of the entire array is greater than 1), it's impossible to make all elements equal to 1, so we return -1.

The total operations needed when starting with no 1s is: (minimum subarray length - 1) to create the first 1, plus (n - 1) to propagate it to all positions.

Learn more about Math patterns.

Solution Approach

The implementation follows a two-phase approach based on whether 1s already exist in the array:

Phase 1: Check for existing 1s

cnt = nums.count(1)
if cnt:
    return n - cnt

First, we count how many 1s are already in the array. If there are any 1s present, we can immediately return n - cnt since each non-1 element needs exactly one operation to become 1 through GCD with an adjacent 1.

Phase 2: Find minimum length subarray with GCD = 1

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

If no 1s exist, we need to create one. We use a nested loop approach:

• The outer loop iterates through each starting position i
• For each starting position, we progressively extend the subarray by including elements at position j
• We maintain a running GCD g of all elements in the current subarray [i, j]
• The property GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) allows us to update the GCD incrementally
• When g becomes 1, we've found a valid subarray of length j - i + 1
• We track the minimum length found in variable mi

Final calculation:

return -1 if mi > n else n - 1 + mi - 1

• If mi > n, no valid subarray was found (impossible case), return -1
• Otherwise, return n - 1 + mi - 1, which simplifies to n + mi - 2:
  • mi - 1 operations to create the first 1 from the minimum length subarray
  • n - 1 operations to propagate this 1 to all other positions

The algorithm has time complexity O(n² × log(max(nums))) where the log factor comes from the GCD computation, and space complexity O(1) as we only use a few variables.

Example Walkthrough

Let's walk through the solution with the array nums = [6, 10, 15].

Step 1: Check for existing 1s

• Count of 1s = 0
• Since there are no 1s, we need to create one first

Step 2: Find minimum length subarray with GCD = 1

We'll check all possible subarrays:

Starting at index 0:

• Subarray [6]: GCD = 6 (not 1)
• Subarray [6, 10]: GCD(6, 10) = 2 (not 1)
• Subarray [6, 10, 15]: GCD(GCD(6, 10), 15) = GCD(2, 15) = 1 ✓
  • Length = 3

Starting at index 1:

• Subarray [10]: GCD = 10 (not 1)
• Subarray [10, 15]: GCD(10, 15) = 5 (not 1)

Starting at index 2:

• Subarray [15]: GCD = 15 (not 1)

Minimum subarray length found = 3

Step 3: Calculate total operations

To create the first 1 from the subarray [6, 10, 15]:

• Operation 1: Replace 6 with GCD(6, 10) = 2 → [2, 10, 15]
• Operation 2: Replace 2 with GCD(2, 15) = 1 → [1, 10, 15]
• This took 3 - 1 = 2 operations

Now propagate the 1 to remaining elements:

• Operation 3: Replace 10 with GCD(1, 10) = 1 → [1, 1, 15]
• Operation 4: Replace 15 with GCD(1, 15) = 1 → [1, 1, 1]
• This took 3 - 1 = 2 more operations

Total operations = (mi - 1) + (n - 1) = 2 + 2 = 4

Using the formula: n + mi - 2 = 3 + 3 - 2 = 4 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of several parts:

• Counting 1s in the array takes O(n) time
• If there are no 1s, we have nested loops:
  • Outer loop runs n times (from i = 0 to n-1)
  • Inner loop runs at most n-i times for each i
  • Inside the inner loop, gcd(g, nums[j]) operation takes O(log(max(nums))) time
  • Since we're looking for the minimum subarray with GCD = 1, in the worst case we examine all O(n²) subarrays

The total time complexity is O(n² × log(max(nums))). However, since the log factor is typically small compared to array operations and the problem constraints usually have bounded values, this is often simplified to O(n²).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables n, cnt, mi, i, j, and g each take O(1) space
• No additional data structures are created
• The gcd function uses O(1) space (iterative implementation) or O(log(min(a,b))) space if recursive, but this doesn't affect the overall complexity

Therefore, the space complexity is O(1) excluding the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect GCD Initialization

A common mistake is initializing the GCD variable incorrectly when computing the GCD of a subarray. Some might initialize it as current_gcd = nums[start_idx] instead of current_gcd = 0.

Why it's wrong: Starting with nums[start_idx] would skip including that element in the GCD calculation for the first iteration.

Correct approach: Initialize with 0 because GCD(0, x) = x for any positive integer x, which correctly includes the first element.

# Wrong
for start_idx in range(n):
    current_gcd = nums[start_idx]  # Incorrect initialization
    for end_idx in range(start_idx + 1, n):  # Skips single element check
        current_gcd = gcd(current_gcd, nums[end_idx])

# Correct
for start_idx in range(n):
    current_gcd = 0  # Correct initialization
    for end_idx in range(start_idx, n):
        current_gcd = gcd(current_gcd, nums[end_idx])

2. Forgetting to Check Single Element Arrays

When the array has only one element, the logic needs special handling. If n = 1 and nums[0] = 1, the answer is 0. If nums[0] ≠ 1, it's impossible (-1).

Solution: The provided code handles this correctly through the initial check for existing 1s and the impossibility check, but it's easy to overlook in custom implementations.

3. Incorrect Final Operation Count

A frequent error is miscalculating the total operations needed when no 1s exist initially.

Common mistakes:

• Returning just min_length - 1 (forgetting to propagate the 1)
• Returning n + min_length (off by one error)
• Returning 2 * (n - 1) (assuming symmetric operations)

Correct formula: (min_length - 1) + (n - 1) where:

• min_length - 1: operations to create the first 1 from the minimum subarray
• n - 1: operations to propagate that 1 to all other positions

4. Breaking Too Early in Subarray Search

Some might break immediately after finding the first subarray with GCD = 1, missing potentially shorter subarrays.

# Wrong - stops at first valid subarray
for i in range(n):
    g = 0
    for j in range(i, n):
        g = gcd(g, nums[j])
        if g == 1:
            return n + (j - i + 1) - 2  # Wrong! Might not be minimum

# Correct - finds minimum length across all valid subarrays
min_length = n + 1
for i in range(n):
    g = 0
    for j in range(i, n):
        g = gcd(g, nums[j])
        if g == 1:
            min_length = min(min_length, j - i + 1)
            break  # Can break here since extending won't give shorter subarray

5. Not Handling the Impossible Case

Forgetting that if the GCD of the entire array is greater than 1, it's impossible to make all elements equal to 1.

Example: For array [2, 4, 6, 8], the GCD of all elements is 2, so no sequence of operations can produce a 1.

Solution: The check if min_length > n: return -1 handles this case, as no valid subarray will be found if the overall GCD > 1.