LeetCode 2654 - Minimum Number of Operations to Make All Array Elements Equal to 1

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

Problem Understanding

The problem gives us an array of positive integers, nums. In one operation, we may choose two adjacent elements, nums[i] and nums[i+1], and replace either one of them with the greatest common divisor, gcd, of the pair.

The goal is to make every element in the array equal to 1 using the minimum number of operations. If it is impossible to produce even a single 1, then the answer must be -1.

The important detail is that each operation only affects adjacent elements. We cannot directly change arbitrary positions. However, the gcd operation has a very useful property:

The gcd of numbers can only stay the same or decrease.
Once a 1 appears, it becomes extremely powerful because gcd(1, x) = 1 for any positive integer x.

This means that if we can create one 1, we can gradually spread that 1 throughout the array by repeatedly applying gcd operations with neighboring elements.

The constraints are relatively small:

2 <= nums.length <= 50
1 <= nums[i] <= 10^6

Since the array length is at most 50, quadratic or even cubic solutions are feasible. We do not need highly optimized advanced data structures.

Several edge cases are important:

If the array already contains one or more 1s, we do not need to create a new 1. We only need to spread existing 1s to the remaining positions.
If the gcd of the entire array is greater than 1, then it is impossible to ever produce a 1, because gcd operations can never reduce below the gcd of all elements.
If no 1 exists initially, we must first find the shortest subarray whose gcd is 1, because that gives the cheapest way to create the first 1.

Approaches

Brute Force Approach

A brute force solution would simulate all possible sequences of operations using breadth first search or exhaustive recursion.

At each step, we could try every adjacent pair and every replacement choice, generating many possible new arrays. Eventually we would search for the minimum number of operations needed to transform the array into all 1s.

This approach is theoretically correct because it explores every possible operation sequence. However, it becomes computationally infeasible very quickly. Each state can branch into many new states, and the total number of possible arrays grows exponentially.

Even with only 50 elements, exhaustive state exploration is far too expensive.

Optimal Observation

The key insight comes from understanding how gcd behaves.

If the array already contains a 1, then every non-one element can be converted into 1 in exactly one operation by taking gcd with a neighboring 1.

Therefore:

If there are already k ones, we need exactly n - k operations.

The harder case occurs when there are no 1s initially.

To create the first 1, we need some contiguous subarray whose gcd becomes 1. Suppose the shortest such subarray has length L.

Reducing a subarray of length L into a single value requires L - 1 gcd operations. After that, we will have one 1 somewhere in the array.

Then we need another n - 1 operations to spread that 1 to every other position.

So the total becomes:

$$(L - 1) + (n - 1)$$

Therefore, the problem reduces to finding the shortest subarray with gcd equal to 1.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible operation sequences
Optimal	O(n² log M)	O(1)	Finds shortest subarray with gcd 1

Here, M is the maximum value in the array, since gcd computation takes logarithmic time.

Algorithm Walkthrough

First, count how many elements in the array are already equal to 1.
If at least one 1 already exists, then we can convert every non-one element into 1 in one operation each. Return n - count_of_ones.
Otherwise, compute the gcd of the entire array incrementally.
If the gcd of the whole array is greater than 1, then it is impossible to ever create a 1. Return -1.
If creating a 1 is possible, search for the shortest subarray whose gcd equals 1.
For every starting index i, initialize current_gcd = nums[i].
Extend the subarray one element at a time using index j. Update:

$$current_gcd = gcd(current_gcd, nums[j])$$ 8. As soon as current_gcd becomes 1, record the subarray length j - i + 1 and stop extending this starting position, because any longer subarray cannot be better. 9. Track the minimum such length across all starting positions. 10. If the shortest valid subarray length is L, then:

L - 1 operations create the first 1
n - 1 operations spread it to all positions

Return:

$$(L - 1) + (n - 1)$$

Why it works

The algorithm works because gcd operations on adjacent elements effectively allow us to reduce a contiguous subarray into its cumulative gcd. A subarray can only produce 1 if its gcd is 1.

The shortest subarray with gcd 1 minimizes the cost of creating the first 1. Once one 1 exists, each remaining element requires exactly one additional operation because gcd(1, x) = 1.

Therefore, the algorithm always computes the minimum possible number of operations.

Python Solution

from typing import List
from math import gcd

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

        ones_count = nums.count(1)

        # If we already have ones, spread them
        if ones_count > 0:
            return n - ones_count

        # Check if it is impossible
        overall_gcd = nums[0]
        for value in nums[1:]:
            overall_gcd = gcd(overall_gcd, value)

        if overall_gcd > 1:
            return -1

        # Find shortest subarray with gcd 1
        min_length = float("inf")

        for left in range(n):
            current_gcd = 0

            for right in range(left, n):
                current_gcd = gcd(current_gcd, nums[right])

                if current_gcd == 1:
                    min_length = min(min_length, right - left + 1)
                    break

        # Operations:
        # (min_length - 1) to create first 1
        # (n - 1) to spread it everywhere
        return (min_length - 1) + (n - 1)

The implementation starts by counting how many 1s already exist. This is an important optimization because existing 1s drastically simplify the problem.

If at least one 1 exists, the answer is immediately n - ones_count, since every non-one element can be converted individually.

If no 1 exists, the code computes the gcd of the entire array. If that gcd is greater than 1, the function returns -1 because creating a 1 is mathematically impossible.

The nested loops then search for the shortest subarray whose gcd becomes 1. The inner loop incrementally updates the gcd instead of recomputing it from scratch, which keeps the implementation efficient.

Finally, the formula:

(min_length - 1) + (n - 1)

combines the cost of creating the first 1 and spreading it across the array.

Go Solution

package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func minOperations(nums []int) int {
	n := len(nums)

	onesCount := 0
	for _, value := range nums {
		if value == 1 {
			onesCount++
		}
	}

	// If there are already ones
	if onesCount > 0 {
		return n - onesCount
	}

	// Compute gcd of entire array
	overallGCD := nums[0]
	for i := 1; i < n; i++ {
		overallGCD = gcd(overallGCD, nums[i])
	}

	// Impossible to create 1
	if overallGCD > 1 {
		return -1
	}

	// Find shortest subarray with gcd 1
	const INF = int(1e9)
	minLength := INF

	for left := 0; left < n; left++ {
		currentGCD := 0

		for right := left; right < n; right++ {
			currentGCD = gcd(currentGCD, nums[right])

			if currentGCD == 1 {
				length := right - left + 1
				if length < minLength {
					minLength = length
				}
				break
			}
		}
	}

	return (minLength - 1) + (n - 1)
}

The Go implementation follows the exact same logic as the Python version. Since Go does not provide a built-in gcd function, we implement Euclid's algorithm manually.

Go slices are used directly, and integer overflow is not a concern because the problem constraints are small. The solution uses only constant extra space besides a few variables.

Worked Examples

Example 1

nums = [2,6,3,4]

Initially, there are no 1s.

Compute gcd of entire array:

Step	Current GCD
gcd(2,6)	2
gcd(2,3)	1
gcd(1,4)	1

Since overall gcd is 1, a solution exists.

Now search for shortest subarray with gcd 1.

Starting at index 0

Subarray	GCD
[2]	2
[2,6]	2
[2,6,3]	1

Length is 3.

Starting at index 1

Subarray	GCD
[6]	6
[6,3]	3
[6,3,4]	1

Length is 3.

Starting at index 2

Subarray	GCD
[3]	3
[3,4]	1

Length is 2.

The shortest length is 2.

Operations needed:

2 - 1 = 1 operation to create first 1
4 - 1 = 3 operations to spread it

Total:

1 + 3 = 4

Answer:

Example 2

nums = [2,10,6,14]

Compute overall gcd:

Step	Current GCD
gcd(2,10)	2
gcd(2,6)	2
gcd(2,14)	2

The overall gcd is 2.

Since the gcd of the entire array is greater than 1, it is impossible to ever produce a 1.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² log M)	Nested loops over subarrays, each gcd takes logarithmic time
Space	O(1)	Only a few variables are used

The outer loop iterates over every starting index, and the inner loop extends subarrays to the right. This creates O(n²) subarray checks. Each gcd computation takes O(log M) time, where M is the maximum array value.

The algorithm uses constant auxiliary space because no additional data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        from math import gcd

        n = len(nums)

        ones_count = nums.count(1)

        if ones_count > 0:
            return n - ones_count

        overall_gcd = nums[0]
        for value in nums[1:]:
            overall_gcd = gcd(overall_gcd, value)

        if overall_gcd > 1:
            return -1

        min_length = float("inf")

        for left in range(n):
            current_gcd = 0

            for right in range(left, n):
                current_gcd = gcd(current_gcd, nums[right])

                if current_gcd == 1:
                    min_length = min(min_length, right - left + 1)
                    break

        return (min_length - 1) + (n - 1)

solution = Solution()

assert solution.minOperations([2, 6, 3, 4]) == 4  # Provided example
assert solution.minOperations([2, 10, 6, 14]) == -1  # Impossible case

assert solution.minOperations([1, 1, 1]) == 0  # Already all ones
assert solution.minOperations([1, 2, 3]) == 2  # Existing one spreads
assert solution.minOperations([2, 3]) == 2  # Need one operation to create 1
assert solution.minOperations([7, 7, 7]) == -1  # Same gcd > 1
assert solution.minOperations([6, 10, 15]) == 4  # Entire array needed
assert solution.minOperations([2, 4, 8, 16, 3]) == 5  # Late gcd reduction
assert solution.minOperations([5, 1, 10, 15]) == 3  # One in middle
assert solution.minOperations([2, 9, 6]) == 3  # Short gcd-1 subarray

Test	Why
`[2,6,3,4]`	Validates standard case
`[2,10,6,14]`	Validates impossible scenario
`[1,1,1]`	Already solved input
`[1,2,3]`	Existing one propagation
`[2,3]`	Smallest nontrivial valid case
`[7,7,7]`	Uniform non-solvable array
`[6,10,15]`	Requires full-array gcd reduction
`[2,4,8,16,3]`	Gcd becomes 1 only near end
`[5,1,10,15]`	One located in middle
`[2,9,6]`	Short subarray produces gcd 1

Edge Cases

One important edge case occurs when the array already contains one or more 1s. A naive implementation might still try to search for gcd-1 subarrays unnecessarily. However, once a 1 exists, every neighboring element can become 1 in a single operation. The implementation handles this immediately with:

if ones_count > 0:
    return n - ones_count

Another important edge case is when the gcd of the entire array is greater than 1. In this situation, no sequence of gcd operations can ever produce 1. This is because gcd operations can never reduce below the gcd shared by all elements. The implementation explicitly checks this before attempting any subarray search.

A third tricky edge case is when the shortest gcd-1 subarray has length greater than 2. Some incorrect solutions assume that any pair with gcd 1 is sufficient. However, arrays like [6,10,15] require using the entire subarray to reduce the gcd to 1. The nested loop correctly checks every possible contiguous subarray and finds the minimum valid length.