leetcode

commit 7c20f971e0ccd3988117d056d4f565c936f7a7b0
parent ba52fe64364e4a40338abaa02ed5aa90069b18f5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 11 Nov 2025 20:56:22 -0700

2654. minimum number of operations to make all array elements equal to 1

Diffstat:
M
min_num_opp_arr_equal_1.c
 | 
41
+++++++++++++++++++++++------------------
M
min_num_opp_arr_equal_1.py
 | 
24
+++++++++++++-----------

2 files changed, 36 insertions(+), 29 deletions(-)
diff --git a/min_num_opp_arr_equal_1.c b/min_num_opp_arr_equal_1.c
@@ -11,34 +11,39 @@
  */
 
 int gcd(int a, int b) {
-  int rem = a % b;
-  if (!rem)
-    return b;
-  return gcd(b, rem);
+  while (b != 0) {
+    int tmp = b;
+    b = a % b;
+    a = tmp;
+  }
+  return a;
 }
 
 int minOperations(int *nums, int numsSize) {
-  int one_cnt = 0;
-  for (int i = 0; i < numsSize; i++)
-    if (nums[i] == 1)
-      one_cnt++;
-  if (one_cnt >= 1)
-    return numsSize - one_cnt;
-  int min_subarr_len = numsSize + 1;
+  int n = 0, g = 0;
   for (int i = 0; i < numsSize; i++) {
     int curr = nums[i];
-    for (int j = i + 1; j < numsSize; j++) {
+    if (curr == 1)
+      n++;
+    g = gcd(g, curr);
+  }
+  if (n > 0)
+    return numsSize - n;
+  if (g > 1)
+    return -1;
+  int min = numsSize;
+  for (int i = 0; i < numsSize; i++) {
+    int curr = 0;
+    for (int j = i; j < numsSize; j++) {
       curr = gcd(curr, nums[j]);
       if (curr == 1) {
-        int curr_n = (j + 1) - i;
-        if (curr_n < min_subarr_len)
-          min_subarr_len = curr_n;
+        if (j - i + 1 < min)
+          min = j - i + 1;
+        break;
       }
-      break;
     }
   }
-  return min_subarr_len <= numsSize ? (min_subarr_len - 1) + (numsSize - 1)
-                                    : -1;
+  return min + numsSize - 2;
 }
 
 int main() {
diff --git a/min_num_opp_arr_equal_1.py b/min_num_opp_arr_equal_1.py
@@ -17,17 +17,19 @@ class Solution(object):
         :type nums: List[int]
         :rtype: int
         """
-        ones_cnt = nums.count(1)
-        if ones_cnt:
-            return len(nums) - ones_cnt
-        diff = float("inf")
-        for i in range(len(nums)):
-            g = nums[i]
-            for j in range(i + 1, len(nums)):
-                g = gcd(g, nums[j])
-                if g == 1:
-                    diff = min(diff, j - i)
-        return -1 if diff == float("inf") else diff + len(nums) - 1
+        n, ones = len(nums), nums.count(1)
+        if ones:
+            return n - ones
+        ans = float("inf")
+        for i in range(n):
+            curr = nums[i]
+            for j in range(i + 1, n):
+                curr = gcd(curr, nums[j])
+                if curr == 1:
+                    ans = min(ans, j - i)
+        if ans == float("inf"):
+            return -1
+        return ans + n - 1
 
 
 if __name__ == "__main__":