Skip to content

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<int>& nums) {
    const int n = nums.size();
    const int ones = ranges::count(nums, 1);
    if (ones > 0)
      return n - ones;

    // the minimum operations 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
    // operations to make the other numbers 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;

    // the minimum operations 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
    // operations to make the other numbers 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

    # the minimum operations 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
    # operations to make the other numbers to 1.
    return -1 if minOps == math.inf else minOps + n - 1