main.cpp

// Source: https://leetcode.com/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1
// Title: Minimum Number of Operations to Make All Array Elements Equal to 1
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// You are given a **0-indexed**array `nums` consisting of **positive** integers. You can do the following operation on the array **any** number of times:
//
// - Select an index `i` such that `0 <= i < n - 1` and replace either of`nums[i]` or `nums[i+1]` with their gcd value.
//
// Return the **minimum** number of operations to make all elements of `nums` equal to `1`. If it is impossible, return `-1`.
//
// The gcd of two integers is the greatest common divisor of the two integers.
//
// **Example 1:**
//
// ```
// Input: nums = [2,6,3,4]
// Output: 4
// Explanation: We can do the following operations:
// - Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].
// - Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].
// - Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].
// - Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].
// ```
//
// **Example 2:**
//
// ```
// Input: nums = [2,10,6,14]
// Output: -1
// Explanation: It can be shown that it is impossible to make all the elements equal to 1.
// ```
//
// **Constraints:**
//
// - `2 <= nums.length <= 50`
// - `1 <= nums[i] <= 10^6`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

// Math + Greedy
//
// If there is 1, use that 1 to convert all other numbers to 1.
//
// If not, find a shortest subarray with gcd 1.
// Then use that 1 to convert all other numbers to 1.
class Solution {
 public:
  int minOperations(vector<int>& nums) {
    int n = nums.size();

    // Count 1
    auto count1 = count(nums.cbegin(), nums.cend(), 1);
    if (count1 > 0) return n - count1;  // has 1

    // Check global GCD
    auto g = 0;
    for (auto num : nums) {
      g = gcd(g, num);
    }
    if (g > 1) return -1;  // impossible

    // Find GCDs
    auto minL = n;
    for (auto i = 0; i < n; ++i) {
      auto g = 0;
      for (auto j = i; j < n; ++j) {
        g = gcd(g, nums[j]);
        if (g == 1) {
          minL = min(minL, j - i + 1);
          break;
        }
      }
    }

    return n + minL - 2;
  }
};