2654. 使數組所有元素變成1的最少操作次數

思路

n為數組長度。

1. 如果數組當中包含cnt1個數字 $1$，那麼就能透過操作n - cnt1次將整個數組都變成 $1$。
2. 如果數組不包含數字 $1$，就要看有沒有辦法通過操作得到數字 $1$，

因為操作都用在相鄰的數字上，就相當於判斷存不存在一個子數組的最大公因數為 $1$，
又因為最大公因數只會變得越來越小，若整個數組的數字取最大公因數都不等於 $1$，
就不可能存在一個子數組，所有數字的最大公因數等於 $1$。

因此，先判斷數組裡面有沒有 $1$，以及整個數組的最大公因數。
假如有 $1$，用它去操作其他數字，答案為n - cnt1
假如沒有 $1$，看能否操作出 $1$，如果能，找出操作出 $1$ 的最小次數，最後加上n - 1（相當於cnt1 = 1的情況）。

程式碼

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int GCD = 0, cnt1 = 0;
        for(int x : nums) {
            GCD = __gcd(GCD, x);
            cnt1 += x == 1;
        }
        if(GCD > 1) { // 沒有 1, 也弄不出 1 
            return -1;
        }
        if(cnt1 > 0) { // 有 1, 用這些 1 去操作其他數字
            return n - cnt1;
        }
        // 弄得出 1
        int mnSize = n;
        for(int i = 0; i < n; ++i) {
            int g = 0;
            for(int j = i; j < n; ++j) { // 從 i 開始, 往後延展, 直到弄出 1 
                g = gcd(g, nums[j]);
                if(g == 1) { // 弄出 1, 紀錄大小
                    mnSize = min(mnSize, j - i + 1);
                    break;
                }
            }
        }
        // 先透過 mnSize - 1次操作，獲取到一個 1, 
        // 再透過 n - 1 次操作讓剩下的數字變成 1 
        return mnSize + n - 2;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(1)$