# 2654. Minimum Number of Operations to Make All Array Elements Equal to 1

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: int minOperations(vector& nums) { const int n = nums.size(); const int ones = count(nums.begin(), nums.end(), 1); if (ones > 0) return n - ones; // ops to make the shortest subarray with a gcd == 1 int minOps = INT_MAX; for (int i = 0; i < n; ++i) { int g = nums[i]; for (int j = i + 1; j < n; ++j) { g = __gcd(g, nums[j]); if (g == 1) { // gcd(nums[i..j]) == 1 minOps = min(minOps, j - i); break; } } } // After making the shortest subarray with minOps, need additional n - 1 // ops to make other nums to 1. return minOps == INT_MAX ? -1 : minOps + n - 1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int minOperations(int[] nums) { final int n = nums.length; final int ones = (int) Arrays.stream(nums).filter(num -> num == 1).count(); if (ones > 0) return n - ones; // ops to make the shortest subarray with a gcd == 1 int minOps = Integer.MAX_VALUE; for (int i = 0; i < n; ++i) { int g = nums[i]; for (int j = i + 1; j < n; ++j) { g = gcd(g, nums[j]); if (g == 1) { // gcd(nums[i..j]) == 1 minOps = Math.min(minOps, j - i); break; } } } // After making the shortest subarray with minOps, need additional n - 1 // ops to make other nums to 1. return minOps == Integer.MAX_VALUE ? -1 : minOps + n - 1; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums) ones = nums.count(1) if ones > 0: return n - ones # ops to make the shortest subarray with a gcd == 1 minOps = math.inf for i, g in enumerate(nums): for j in range(i + 1, n): g = math.gcd(g, nums[j]) if g == 1: # gcd(nums[i..j]:== 1 minOps = min(minOps, j - i) break # After making the shortest subarray with minOps, need additional n - 1 # ops to make other nums to 1. return -1 if minOps == math.inf else minOps + n - 1