Minimum Number of Operations to Make All Array Elements Equal to 1

main.md

Question

Approach

I first check if any element is already 1. If so, each other element can be turned into 1 with one operation by repeatedly using adjacent 1s, so the minimum operations equals the number of elements that are not 1. If no 1 exists, I try to create a 1 by taking gcds inside a subarray. For a subarray of length L, it takes L-1 operations to reduce that subarray to a single 1. After creating that 1, we still need n-1 operations to turn the remaining n-1 elements into 1. So if the smallest subarray whose gcd is 1 has length L, the total minimum operations is (L-1) + (n-1). If no subarray has gcd 1 then it is impossible and we return -1.

Implementation

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        non_ones = sum(1 for v in nums if v != 1)
        if non_ones < n:
            return non_ones
        
        best = float('inf')
        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    best = min(best, j - i + 1)
                    break
        
        if best == float('inf'):
            return -1
        
        return (best - 1) + (n - 1)

Complexities

• Time: O(n^2)
• Space: O(1)