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

Description

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⁶

Solutions

Solution 1: Math

We first count the number of \(1\)s in the array \(nums\) as \(cnt\). If \(cnt \gt 0\), then we only need \(n - cnt\) operations to turn the entire array into \(1\)s.

Otherwise, we need to first turn one element in the array into \(1\), and then the minimum number of remaining operations is \(n - 1\).

Consider how to turn one element in the array into \(1\) while minimizing the number of operations. In fact, we only need to find a minimum contiguous subarray interval \(nums[i,..j]\) such that the greatest common divisor of all elements in the subarray is \(1\), with the subarray length being \(mi = \min(mi, j - i + 1)\). Finally, our total number of operations is \(n - 1 + mi - 1\).

The time complexity is \(O(n \times (n + \log M))\) and the space complexity is \(O(\log M)\), where \(n\) and \(M\) are the length of the array \(nums\) and the maximum value in the array \(nums\), respectively.

Python3JavaC++GoTypeScriptRust

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = nums.count(1)
        if cnt:
            return n - cnt
        mi = n + 1
        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    mi = min(mi, j - i + 1)
        return -1 if mi > n else n - 1 + mi - 1

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for (int x : nums) {
            if (x == 1) {
                ++cnt;
            }
        }
        if (cnt > 0) {
            return n - cnt;
        }
        int mi = n + 1;
        for (int i = 0; i < n; ++i) {
            int g = 0;
            for (int j = i; j < n; ++j) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    mi = Math.min(mi, j - i + 1);
                }
            }
        }
        return mi > n ? -1 : n - 1 + mi - 1;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int cnt = 0;
        for (int x : nums) {
            if (x == 1) {
                ++cnt;
            }
        }
        if (cnt) {
            return n - cnt;
        }
        int mi = n + 1;
        for (int i = 0; i < n; ++i) {
            int g = 0;
            for (int j = i; j < n; ++j) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    mi = min(mi, j - i + 1);
                }
            }
        }
        return mi > n ? -1 : n - 1 + mi - 1;
    }
};

func minOperations(nums []int) int {
    n := len(nums)
    cnt := 0
    for _, x := range nums {
        if x == 1 {
            cnt++
        }
    }
    if cnt > 0 {
        return n - cnt
    }
    mi := n + 1
    for i := 0; i < n; i++ {
        g := 0
        for j := i; j < n; j++ {
            g = gcd(g, nums[j])
            if g == 1 {
                mi = min(mi, j-i+1)
            }
        }
    }
    if mi > n {
        return -1
    }
    return n - 1 + mi - 1
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

function minOperations(nums: number[]): number {
    const n = nums.length;
    let cnt = 0;
    for (const x of nums) {
        if (x === 1) {
            ++cnt;
        }
    }
    if (cnt > 0) {
        return n - cnt;
    }
    let mi = n + 1;
    for (let i = 0; i < n; ++i) {
        let g = 0;
        for (let j = i; j < n; ++j) {
            g = gcd(g, nums[j]);
            if (g === 1) {
                mi = Math.min(mi, j - i + 1);
            }
        }
    }
    return mi > n ? -1 : n - 1 + mi - 1;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let cnt = nums.iter().filter(|&&x| x == 1).count() as i32;
        if cnt > 0 {
            return n - cnt;
        }
        let mut mi = n + 1;
        for i in 0..nums.len() {
            let mut g = 0;
            for j in i..nums.len() {
                g = gcd(g, nums[j]);
                if g == 1 {
                    mi = mi.min((j - i + 1) as i32);
                    break;
                }
            }
        }
        if mi > n {
            -1
        } else {
            n - 1 + mi - 1
        }
    }
}

fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let tmp = a % b;
        a = b;
        b = tmp;
    }
    a.abs()
}

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

Description

Solutions

Solution 1: Math

Comments