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

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums 要求在进行一系列操作后将数组元素全部变成 1

操作描述：随意抓取相邻的两个元素，计算他们的最大公因数，然后将其中一个转变成求出的最大公因数

题目要求我们返回可能的最少操作数，如果不可能将所有元素都变成 1，则返回 -1

解题思路

根据题意，我们要把整个数组都变成 1，首先必须把其中一个元素变成 1（因为 1 跟其他数字的最大公因数都是 1）

把数组元素变成 1 的情况总共有三种：

1. 元素本身就是 1
2. 两个相邻元素最大公因数是 1
3. 存在一个子数组，其中的所有元素的最大公因数是 1

第一种情况下，我们把所有元素变成 1 所需的最少操作是 nums.length - countOne，其中 countOne 是数组中 1 的个数

第二种情况跟第三种情况类似，我们合并讨论，在这种情况下我们需要的操作分别有：

1. 假设子数组长度是 subNumLen，我们需要 subNumLen - 1 次操作把其中一个元素变为 1
2. 一旦其中一个元素是 1 后，我们需要 nums.length - 1 次操作把剩下的元素变为 1

两者相加，就是 subNumLen - 1 + nums.length - 1 次操作

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
    let allGCD = 0
    const len = nums.length
    let countOne = 0
    for (let i = 0; i < len; i++) {
        if (nums[i] === 1) {
            countOne++
        }
        allGCD = gcd(allGCD, nums[i])
    }

    if (countOne > 0) {
        return len - countOne
    }
    // we cannot change any num to 1
    if (allGCD > 1) {
        return -1
    }

    let subNumLen = len
    for (let i = 0; i < len; i++) {
        let curGcd = 0
        for (let j = i; j < len; j++) {
            curGcd = gcd(curGcd, nums[j])
            if (curGcd === 1) {
                subNumLen = Math.min(subNumLen, j - i + 1)
            }
        }
    }

    return len - 1 + subNumLen - 1



};

const gcd = (a, b) => {
    while (b !== 0) {
        let temp = b
        b = a % b
        a = temp
    }
    return a
}